<?xml version='1.0' encoding='UTF-8'?>
<!DOCTYPE html PUBLIC '-//W3C//DTD XHTML 1.0 Transitional//EN' 'http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd'>
<html dir="ltr" xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>The JSON-LD API 1.0</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />

<!-- 
  === NOTA BENE ===
  For the three scripts below, if your spec resides on dev.w3 you can check them
  out in the same tree and use relative links so that they'll work offline,
   -->



<style>
.diff { font-weight:bold; color:#0a3; }
ol.algorithm.update { margin-left: 2em; }
ol.algorithm.update<li { list-style-type: none; }
ol.algorithm.update<li<span.list-number {
  display:block;
  float: left;
  margin-left: -3.5em;
}
</style>
<style type="text/css">
/*****************************************************************
 * ReSpec CSS
 * Robin Berjon (robin at berjon dot com)
 * v0.05 - 2009-07-31
 *****************************************************************/


/* --- INLINES --- */
em.rfc2119 { 
    text-transform:     lowercase;
    font-variant:       small-caps;
    font-style:         normal;
    color:              #900;
}

h1 acronym, h2 acronym, h3 acronym, h4 acronym, h5 acronym, h6 acronym, a acronym,
h1 abbr, h2 abbr, h3 abbr, h4 abbr, h5 abbr, h6 abbr, a abbr {
    border: none;
}

dfn {
    font-weight:    bold;
}

a.internalDFN {
    color:  inherit;
    border-bottom:  1px solid #99c;
    text-decoration:    none;
}

a.externalDFN {
    color:  inherit;
    border-bottom:  1px dotted #ccc;
    text-decoration:    none;
}

a.bibref {
    text-decoration:    none;
}

code {
    color:  #ff4500;
}


/* --- WEB IDL --- */
pre.idl {
    border-top: 1px solid #90b8de;
    border-bottom: 1px solid #90b8de;
    padding:    1em;
    line-height:    120%;
}

pre.idl::before {
    content:    &quot;WebIDL&quot;;
    display:    block;
    width:      150px;
    background: #90b8de;
    color:  #fff;
    font-family:    initial;
    padding:    3px;
    font-weight:    bold;
    margin: -1em 0 1em -1em;
}

.idlType {
    color:  #ff4500;
    font-weight:    bold;
    text-decoration:    none;
}

/*.idlModule*/
/*.idlModuleID*/
/*.idlInterface*/
.idlInterfaceID, .idlDictionaryID {
    font-weight:    bold;
    color:  #005a9c;
}

.idlSuperclass {
    font-style: italic;
    color:  #005a9c;
}

/*.idlAttribute*/
.idlAttrType, .idlFieldType, .idlMemberType {
    color:  #005a9c;
}
.idlAttrName, .idlFieldName, .idlMemberName {
    color:  #ff4500;
}
.idlAttrName a, .idlFieldName a, .idlMemberName a {
    color:  #ff4500;
    border-bottom:  1px dotted #ff4500;
    text-decoration: none;
}

/*.idlMethod*/
.idlMethType {
    color:  #005a9c;
}
.idlMethName {
    color:  #ff4500;
}
.idlMethName a {
    color:  #ff4500;
    border-bottom:  1px dotted #ff4500;
    text-decoration: none;
}

/*.idlParam*/
.idlParamType {
    color:  #005a9c;
}
.idlParamName {
    font-style: italic;
}

.extAttr {
    color:  #666;
}

/*.idlConst*/
.idlConstType {
    color:  #005a9c;
}
.idlConstName {
    color:  #ff4500;
}
.idlConstName a {
    color:  #ff4500;
    border-bottom:  1px dotted #ff4500;
    text-decoration: none;
}

/*.idlException*/
.idlExceptionID {
    font-weight:    bold;
    color:  #c00;
}

.idlTypedefID, .idlTypedefType {
    color:  #005a9c;
}

.idlRaises, .idlRaises a.idlType, .idlRaises a.idlType code, .excName a, .excName a code {
    color:  #c00;
    font-weight:    normal;
}

.excName a {
    font-family:    monospace;
}

.idlRaises a.idlType, .excName a.idlType {
    border-bottom:  1px dotted #c00;
}

.excGetSetTrue, .excGetSetFalse, .prmNullTrue, .prmNullFalse, .prmOptTrue, .prmOptFalse {
    width:  45px;
    text-align: center;
}
.excGetSetTrue, .prmNullTrue, .prmOptTrue { color:  #0c0; }
.excGetSetFalse, .prmNullFalse, .prmOptFalse { color:  #c00; }

.idlImplements a {
    font-weight:    bold;
}

dl.attributes, dl.methods, dl.constants, dl.fields, dl.dictionary-members {
    margin-left:    2em;
}

.attributes dt, .methods dt, .constants dt, .fields dt, .dictionary-members dt {
    font-weight:    normal;
}

.attributes dt code, .methods dt code, .constants dt code, .fields dt code, .dictionary-members dt code {
    font-weight:    bold;
    color:  #000;
    font-family:    monospace;
}

.attributes dt code, .fields dt code, .dictionary-members dt code {
    background:  #ffffd2;
}

.attributes dt .idlAttrType code, .fields dt .idlFieldType code, .dictionary-members dt .idlMemberType code {
    color:  #005a9c;
    background:  transparent;
    font-family:    inherit;
    font-weight:    normal;
    font-style: italic;
}

.methods dt code {
    background:  #d9e6f8;
}

.constants dt code {
    background:  #ddffd2;
}

.attributes dd, .methods dd, .constants dd, .fields dd, .dictionary-members dd {
    margin-bottom:  1em;
}

table.parameters, table.exceptions {
    border-spacing: 0;
    border-collapse:    collapse;
    margin: 0.5em 0;
    width:  100%;
}
table.parameters { border-bottom:  1px solid #90b8de; }
table.exceptions { border-bottom:  1px solid #deb890; }

.parameters th, .exceptions th {
    color:  #fff;
    padding:    3px 5px;
    text-align: left;
    font-family:    initial;
    font-weight:    normal;
    text-shadow:    #666 1px 1px 0;
}
.parameters th { background: #90b8de; }
.exceptions th { background: #deb890; }

.parameters td, .exceptions td {
    padding:    3px 10px;
    border-top: 1px solid #ddd;
    vertical-align: top;
}

.parameters tr:first-child td, .exceptions tr:first-child td {
    border-top: none;
}

.parameters td.prmName, .exceptions td.excName, .exceptions td.excCodeName {
    width:  100px;
}

.parameters td.prmType {
    width:  120px;
}

table.exceptions table {
    border-spacing: 0;
    border-collapse:    collapse;
    width:  100%;
}

/* --- TOC --- */
.toc a {
    text-decoration:    none;
}

a .secno {
    color:  #000;
}

/* --- TABLE --- */
table.simple {
    border-spacing: 0;
    border-collapse:    collapse;
    border-bottom:  3px solid #005a9c;
}

.simple th {
    background: #005a9c;
    color:  #fff;
    padding:    3px 5px;
    text-align: left;
}

.simple th[scope=&quot;row&quot;] {
    background: inherit;
    color:  inherit;
    border-top: 1px solid #ddd;
}

.simple td {
    padding:    3px 10px;
    border-top: 1px solid #ddd;
}

.simple tr:nth-child(even) {
    background: #f0f6ff;
}

/* --- DL --- */
.section dd &gt; p:first-child {
    margin-top: 0;
}

.section dd &gt; p:last-child {
    margin-bottom: 0;
}

.section dd {
    margin-bottom:  1em;
}

.section dl.attrs dd, .section dl.eldef dd {
    margin-bottom:  0;
}

/* --- EXAMPLES --- */
pre.example {
    border-top: 1px solid #ff4500;
    border-bottom: 1px solid #ff4500;
    padding:    1em;
    margin-top: 1em;
}

pre.example::before {
    content:    &quot;Example&quot;;
    display:    block;
    width:      150px;
    background: #ff4500;
    color:  #fff;
    font-family:    initial;
    padding:    3px;
    font-weight:    bold;
    margin: -1em 0 1em -1em;
}

/* --- EDITORIAL NOTES --- */
.issue {
    padding:    1em;
    margin: 1em 0em 0em;
    border: 1px solid #f00;
    background: #ffc;
}

.issue::before {
    content:    &quot;Issue&quot;;
    display:    block;
    width:  150px;
    margin: -1.5em 0 0.5em 0;
    font-weight:    bold;
    border: 1px solid #f00;
    background: #fff;
    padding:    3px 1em;
}

.note {
    margin: 1em 0em 0em;
    padding:    1em;
    border: 2px solid #cff6d9;
    background: #e2fff0;
}

.note::before {
    content:    &quot;Note&quot;;
    display:    block;
    width:  150px;
    margin: -1.5em 0 0.5em 0;
    font-weight:    bold;
    border: 1px solid #cff6d9;
    background: #fff;
    padding:    3px 1em;
}

/* --- Best Practices --- */
div.practice {
    border: solid #bebebe 1px;
    margin: 2em 1em 1em 2em;
}

span.practicelab {
    margin: 1.5em 0.5em 1em 1em;
    font-weight: bold;
    font-style: italic;
}

span.practicelab   { background: #dfffff; }

span.practicelab {
    position: relative;
    padding: 0 0.5em;
    top: -1.5em;
}

p.practicedesc {
    margin: 1.5em 0.5em 1em 1em;
}

@media screen {
    p.practicedesc {
        position: relative;
        top: -2em;
        padding: 0;
        margin: 1.5em 0.5em -1em 1em;
    }
}

/* --- SYNTAX HIGHLIGHTING --- */
pre.sh_sourceCode {
  background-color: white;
  color: black;
  font-style: normal;
  font-weight: normal;
}

pre.sh_sourceCode .sh_keyword { color: #005a9c; font-weight: bold; }           /* language keywords */
pre.sh_sourceCode .sh_type { color: #666; }                            /* basic types */
pre.sh_sourceCode .sh_usertype { color: teal; }                             /* user defined types */
pre.sh_sourceCode .sh_string { color: red; font-family: monospace; }        /* strings and chars */
pre.sh_sourceCode .sh_regexp { color: orange; font-family: monospace; }     /* regular expressions */
pre.sh_sourceCode .sh_specialchar { color: 	#ffc0cb; font-family: monospace; }  /* e.g., \n, \t, \\ */
pre.sh_sourceCode .sh_comment { color: #A52A2A; font-style: italic; }         /* comments */
pre.sh_sourceCode .sh_number { color: purple; }                             /* literal numbers */
pre.sh_sourceCode .sh_preproc { color: #00008B; font-weight: bold; }       /* e.g., #include, import */
pre.sh_sourceCode .sh_symbol { color: blue; }                            /* e.g., *, + */
pre.sh_sourceCode .sh_function { color: black; font-weight: bold; }         /* function calls and declarations */
pre.sh_sourceCode .sh_cbracket { color: red; }                              /* block brackets (e.g., {, }) */
pre.sh_sourceCode .sh_todo { font-weight: bold; background-color: #00FFFF; }   /* TODO and FIXME */

/* Predefined variables and functions (for instance glsl) */
pre.sh_sourceCode .sh_predef_var { color: #00008B; }
pre.sh_sourceCode .sh_predef_func { color: #00008B; font-weight: bold; }

/* for OOP */
pre.sh_sourceCode .sh_classname { color: teal; }

/* line numbers (not yet implemented) */
pre.sh_sourceCode .sh_linenum { display: none; }

/* Internet related */
pre.sh_sourceCode .sh_url { color: blue; text-decoration: underline; font-family: monospace; }

/* for ChangeLog and Log files */
pre.sh_sourceCode .sh_date { color: blue; font-weight: bold; }
pre.sh_sourceCode .sh_time, pre.sh_sourceCode .sh_file { color: #00008B; font-weight: bold; }
pre.sh_sourceCode .sh_ip, pre.sh_sourceCode .sh_name { color: #006400; }

/* for Prolog, Perl... */
pre.sh_sourceCode .sh_variable { color: #006400; }

/* for LaTeX */
pre.sh_sourceCode .sh_italics { color: #006400; font-style: italic; }
pre.sh_sourceCode .sh_bold { color: #006400; font-weight: bold; }
pre.sh_sourceCode .sh_underline { color: #006400; text-decoration: underline; }
pre.sh_sourceCode .sh_fixed { color: green; font-family: monospace; }
pre.sh_sourceCode .sh_argument { color: #006400; }
pre.sh_sourceCode .sh_optionalargument { color: purple; }
pre.sh_sourceCode .sh_math { color: orange; }
pre.sh_sourceCode .sh_bibtex { color: blue; }

/* for diffs */
pre.sh_sourceCode .sh_oldfile { color: orange; }
pre.sh_sourceCode .sh_newfile { color: #006400; }
pre.sh_sourceCode .sh_difflines { color: blue; }

/* for css */
pre.sh_sourceCode .sh_selector { color: purple; }
pre.sh_sourceCode .sh_property { color: blue; }
pre.sh_sourceCode .sh_value { color: #006400; font-style: italic; }

/* other */
pre.sh_sourceCode .sh_section { color: black; font-weight: bold; }
pre.sh_sourceCode .sh_paren { color: red; }
pre.sh_sourceCode .sh_attribute { color: #006400; }

</style><style type="text/css">ol.algorithm { counter-reset:numsection; list-style-type: none; }
ol.algorithm li { margin: 0.5em 0; }
ol.algorithm li:before { font-weight: bold; counter-increment: numsection; content: counters(numsection, ".") ") "; }

</style><link href="http://www.w3.org/StyleSheets/TR/w3c-unofficial" rel="stylesheet" type="text/css" charset="utf-8" /></head>

<body style="display: inherit; "><div class="head"><p></p><h1 class="title" id="title">The JSON-LD API 1.0</h1><h2 id="subtitle">An Application Programming Interface for the JSON-LD Syntax</h2><h2 id="unofficial-draft-16-october-2011">Unofficial Draft 16 October 2011</h2><dl><dt>Editors:</dt><dd><a href="http://manu.sporny.org/">Manu Sporny</a>, <a href="http://digitalbazaar.com/">Digital Bazaar</a></dd>
<dd><a href="http://greggkellogg.net/">Gregg Kellogg</a>, Kellogg Associates</dd>
<dd><a href="http://digitalbazaar.com/">Dave Longley</a>, <a href="http://digitalbazaar.com/">Digital Bazaar</a></dd>
<dt>Authors:</dt><dd><a href="http://digitalbazaar.com/">Dave Longley</a>, <a href="http://digitalbazaar.com/">Digital Bazaar</a></dd>
<dd><a href="http://digitalbazaar.com/">Manu Sporny</a>, <a href="http://digitalbazaar.com/">Digital Bazaar</a></dd>
<dd><a href="http://greggkellogg.net/">Gregg Kellogg</a>, Kellogg Associates</dd>
</dl><p class="copyright">This document is licensed under a <a class="subfoot" href="http://creativecommons.org/licenses/by/3.0/" rel="license">Creative Commons Attribution 3.0 License</a>.</p><hr /></div>
<div id="abstract" class="introductory section"><h2>Abstract</h2>
<p>
JSON [<cite><a class="bibref" rel="biblioentry" href="#bib-RFC4627">RFC4627</a></cite>] has proven to be a highly useful object serialization and
messaging format. JSON-LD [<cite><a class="bibref" rel="biblioentry" href="#bib-JSON-LD">JSON-LD</a></cite>] harmonizes the representation of 
Linked Data in JSON by outlining a common JSON representation format for
expressing directed graphs; mixing both Linked Data and non-Linked Data in
a single document. This document outlines an Application Programming
Interface and a set of algorithms for programmatically transforming 
JSON-LD documents.
</p>
</div><div id="sotd" class="introductory section"><h2>Status of This Document</h2><p>This document is merely a public working draft of a potential specification. It has no official standing of any kind and does not represent the support or consensus of any standards organisation.</p>
<p>This document is an experimental work in progress.</p>

<!--  <p>
This document has been reviewed by W3C Members, by software
developers, and by other W3C groups and interested parties, and is
endorsed by the Director as a W3C Recommendation. It is a stable
document and may be used as reference material or cited from another
document. W3C's role in making the Recommendation is to draw attention
to the specification and to promote its widespread deployment. This
enhances the functionality and interoperability of the Web.
</p>  -->

</div><div id="toc" class="section"><h2 class="introductory">Table of Contents</h2><ul class="toc"><li class="tocline"><a href="#introduction" class="tocxref"><span class="secno">1. </span>Introduction</a><ul class="toc"><li class="tocline"><a href="#how-to-read-this-document" class="tocxref"><span class="secno">1.1 </span>How to Read this Document</a></li><li class="tocline"><a href="#contributing" class="tocxref"><span class="secno">1.2 </span>Contributing</a></li></ul></li><li class="tocline"><a href="#the-application-programming-interface" class="tocxref"><span class="secno">2. </span>The Application Programming Interface</a><ul class="toc"><li class="tocline"><a href="#jsonldprocessor" class="tocxref"><span class="secno">2.1 </span>JsonLdProcessor</a><ul class="toc"><li class="tocline"><a href="#methods" class="tocxref"><span class="secno">2.1.1 </span>Methods</a></li></ul></li><li class="tocline"><a href="#jsonldtriplecallback" class="tocxref"><span class="secno">2.2 </span>JsonLdTripleCallback</a><ul class="toc"><li class="tocline"><a href="#methods-1" class="tocxref"><span class="secno">2.2.1 </span>Methods</a></li></ul></li></ul></li><li class="tocline"><a href="#algorithms" class="tocxref"><span class="secno">3. </span>Algorithms</a><ul class="toc"><li class="tocline"><a href="#syntax-tokens-and-keywords" class="tocxref"><span class="secno">3.1 </span>Syntax Tokens and Keywords</a></li><li class="tocline"><a href="#algorithm-terms" class="tocxref"><span class="secno">3.2 </span>Algorithm Terms</a></li><li class="tocline"><a href="#context-1" class="tocxref"><span class="secno">3.3 </span>Context</a><ul class="toc"><li class="tocline"><a href="#coerce" class="tocxref"><span class="secno">3.3.1 </span>Coerce</a></li><li class="tocline"><a href="#initial-context" class="tocxref"><span class="secno">3.3.2 </span>Initial Context</a></li></ul></li><li class="tocline"><a href="#iri-expansion" class="tocxref"><span class="secno">3.4 </span>IRI Expansion</a></li><li class="tocline"><a href="#iri-compaction" class="tocxref"><span class="secno">3.5 </span>IRI Compaction</a></li><li class="tocline"><a href="#value-expansion" class="tocxref"><span class="secno">3.6 </span>Value Expansion</a></li><li class="tocline"><a href="#value-compaction" class="tocxref"><span class="secno">3.7 </span>Value Compaction</a></li><li class="tocline"><a href="#expansion" class="tocxref"><span class="secno">3.8 </span>Expansion</a><ul class="toc"><li class="tocline"><a href="#expansion-algorithm" class="tocxref"><span class="secno">3.8.1 </span>Expansion Algorithm</a></li></ul></li><li class="tocline"><a href="#compaction" class="tocxref"><span class="secno">3.9 </span>Compaction</a><ul class="toc"><li class="tocline"><a href="#compaction-algorithm" class="tocxref"><span class="secno">3.9.1 </span>Compaction Algorithm</a></li></ul></li><li class="tocline"><a href="#framing" class="tocxref"><span class="secno">3.10 </span>Framing</a><ul class="toc"><li class="tocline"><a href="#framing-algorithm-terms" class="tocxref"><span class="secno">3.10.1 </span>Framing Algorithm Terms</a></li><li class="tocline"><a href="#framing-algorithm" class="tocxref"><span class="secno">3.10.2 </span>Framing Algorithm</a></li></ul></li><li class="tocline"><a href="#normalization" class="tocxref"><span class="secno">3.11 </span>Normalization</a><ul class="toc"><li class="tocline"><a href="#normalization-algorithm-terms" class="tocxref"><span class="secno">3.11.1 </span>Normalization Algorithm Terms</a></li><li class="tocline"><a href="#normalization-state" class="tocxref"><span class="secno">3.11.2 </span>Normalization State</a></li><li class="tocline"><a href="#normalization-algorithm" class="tocxref"><span class="secno">3.11.3 </span>Normalization Algorithm</a></li><li class="tocline"><a href="#node-relabeling-algorithm" class="tocxref"><span class="secno">3.11.4 </span>Node Relabeling Algorithm</a></li><li class="tocline"><a href="#deterministic-labeling-algorithm" class="tocxref"><span class="secno">3.11.5 </span>Deterministic Labeling Algorithm</a></li><li class="tocline"><a href="#shallow-comparison-algorithm" class="tocxref"><span class="secno">3.11.6 </span>Shallow Comparison Algorithm</a></li><li class="tocline"><a href="#object-comparison-algorithm" class="tocxref"><span class="secno">3.11.7 </span>Object Comparison Algorithm</a></li><li class="tocline"><a href="#deep-comparison-algorithm" class="tocxref"><span class="secno">3.11.8 </span>Deep Comparison Algorithm</a></li><li class="tocline"><a href="#node-serialization-algorithm" class="tocxref"><span class="secno">3.11.9 </span>Node Serialization Algorithm</a></li><li class="tocline"><a href="#serialization-label-generation-algorithm" class="tocxref"><span class="secno">3.11.10 </span>Serialization Label Generation Algorithm</a></li><li class="tocline"><a href="#combinatorial-serialization-algorithm" class="tocxref"><span class="secno">3.11.11 </span>Combinatorial Serialization Algorithm</a></li><li class="tocline"><a href="#serialization-comparison-algorithm" class="tocxref"><span class="secno">3.11.12 </span>Serialization Comparison Algorithm</a></li><li class="tocline"><a href="#mapping-serialization-algorithm" class="tocxref"><span class="secno">3.11.13 </span>Mapping Serialization Algorithm</a></li><li class="tocline"><a href="#label-serialization-algorithm" class="tocxref"><span class="secno">3.11.14 </span>Label Serialization Algorithm</a></li></ul></li><li class="tocline"><a href="#data-round-tripping" class="tocxref"><span class="secno">3.12 </span>Data Round Tripping</a></li><li class="tocline"><a href="#rdf-conversion" class="tocxref"><span class="secno">3.13 </span>RDF Conversion</a><ul class="toc"><li class="tocline"><a href="#overview" class="tocxref"><span class="secno">3.13.1 </span>Overview</a></li><li class="tocline"><a href="#rdf-conversion-algorithm-terms" class="tocxref"><span class="secno">3.13.2 </span>RDF Conversion Algorithm Terms</a></li><li class="tocline"><a href="#rdf-conversion-algorithm" class="tocxref"><span class="secno">3.13.3 </span>RDF Conversion Algorithm</a></li><li class="tocline"><a href="#acknowledgements" class="tocxref"><span class="secno">3.13.4 </span>Acknowledgements</a></li></ul></li></ul></li><li class="tocline"><a href="#references" class="tocxref"><span class="secno">A. </span>References</a><ul class="toc"><li class="tocline"><a href="#normative-references" class="tocxref"><span class="secno">A.1 </span>Normative references</a></li><li class="tocline"><a href="#informative-references" class="tocxref"><span class="secno">A.2 </span>Informative references</a></li></ul></li></ul></div>



<div id="introduction" class="section">

<!-- OddPage -->
<h2><span class="secno">1. </span>Introduction</h2>

<p>
JSON, as specified in [<cite><a class="bibref" rel="biblioentry" href="#bib-RFC4627">RFC4627</a></cite>], is a simple language for representing
data on the Web. Linked Data is a technique for creating a graph of interlinked data across
different
documents or Web sites. Data entities are described using <a class="tref" title="IRI">IRI</a>s,
which are typically dereferencable and thus may be used to find more
information about an entity, creating a &quot;Web of Knowledge&quot;. JSON-LD is intended to be a simple
publishing method for expressing not only Linked Data in JSON, but also for adding
semantics to existing JSON.
</p>

<p>
JSON-LD is designed as a light-weight syntax that can be used to express
Linked Data. It is primarily intended to be a way to use Linked Data
in Javascript and other Web-based programming environments. It is also
useful when building interoperable Web services and when storing Linked
Data in JSON-based document storage engines. It is practical and designed
to be as simple as possible, utilizing the large number of JSON parsers
and libraries available today. It is designed to be able to
express key-value pairs, RDF data, RDFa [<cite><a class="bibref" rel="biblioentry" href="#bib-RDFA-CORE">RDFA-CORE</a></cite>] data, Microformats
[<cite><a class="bibref" rel="biblioentry" href="#bib-MICROFORMATS">MICROFORMATS</a></cite>] data, and Microdata [<cite><a class="bibref" rel="biblioentry" href="#bib-MICRODATA">MICRODATA</a></cite>]. That is, it supports
every major Web-based structured data model in use today.
</p>

<p>
The syntax does not necessarily require applications to change their JSON, but
allows to easily add meaning by adding context in a way that is either in-band or
out-of-band. The syntax is designed to not disturb already deployed systems
running on JSON, but provide a smooth upgrade path from JSON to JSON with
added semantics. Finally, the format is intended to be easy to parse, efficient to
generate, convertible to RDF in one pass, and require a very small memory footprint
in order to operate.
</p>

<div id="how-to-read-this-document" class="section">
<h3><span class="secno">1.1 </span>How to Read this Document</h3>

<p>
This document is a detailed specification for a serialization of Linked
Data in JSON. The document is primarily intended for the following audiences:
</p>

<ul>
  <li>Authors that want a very detailed view of how JSON-LD processors 
  operate.</li>
  <li>Software developers that want to implement processors and APIs for
  JSON-LD.</li>
</ul>

<p>
To understand the basics in this specification you must first be familiar with
JSON, which is detailed in [<cite><a class="bibref" rel="biblioentry" href="#bib-RFC4627">RFC4627</a></cite>]. You must also understand the
JSON-LD Syntax [<cite><a class="bibref" rel="biblioentry" href="#bib-JSON-LD">JSON-LD</a></cite>], which is the base syntax used by all of the
algorithms in this document. To understand the API and how it is
intended to operate  in a programming environment, it is useful to have working
knowledge of the JavaScript programming language [<cite><a class="bibref" rel="biblioentry" href="#bib-ECMA-262">ECMA-262</a></cite>] and
WebIDL [<cite><a class="bibref" rel="biblioentry" href="#bib-WEBIDL">WEBIDL</a></cite>]. To understand how JSON-LD maps to RDF, it is helpful to be
familiar with the basic RDF concepts [<cite><a class="bibref" rel="biblioentry" href="#bib-RDF-CONCEPTS">RDF-CONCEPTS</a></cite>].</p>

<p>
  Examples may contain references to existing vocabularies and use <a class="tref" title="prefix">prefix</a>es to refer to Web Vocabularies. The following is a list of all vocabularies and their <a class="tref" title="prefix">prefix</a> abbreviations, as used in this document:
</p>
<ul>
  <li>The <a href="http://purl.org/dc/terms/">Dublin Core</a>
  vocabulary (abbreviation: <code>dc</code>, e.g., <code>dc:title</code>)</li>
  <li>The <a href="http://xmlns.com/foaf/0.1/">Friend of a Friend</a>
  vocabulary (abbreviation: <code>foaf</code>, e.g., <code>foaf:knows</code>)</li>
  <li>The <a href="http://www.w3.org/1999/02/22-rdf-syntax-ns#">RDF</a>
  vocabulary (abbreviation: <code>rdf</code>, e.g., <code>rdf:type</code>)</li>
  <li>The <a href="http://www.w3.org/2001/XMLSchema#">XSD</a>
  vocabulary (abbreviation: <code>xsd</code>, e.g., <code>xsd:integer</code>)</li>
</ul>

<p>
  JSON [<cite><a class="bibref" rel="biblioentry" href="#bib-RFC4627">RFC4627</a></cite>] defines several terms which are used throughout this document:
  </p><dl>
    <dt><dfn title="JSON_Object" id="dfn-json_object">JSON Object</dfn></dt><dd>
      An object structure is represented as a pair of curly brackets surrounding zero or
      more name/value pairs (or members). A name is a <a class="tref internalDFN" title="string" href="#dfn-string">string</a>. A single colon comes after
      each name, separating the name from the value. A single comma separates a value
      from a following name. The names within an object <em class="rfc2119" title="should">should</em> be unique.
    </dd>
    <dt><dfn title="array" id="dfn-array">array</dfn></dt>
    <dd>
      An array is an ordered collection of values. An array structure is represented as square brackets surrounding zero or more values (or elements). Elements are separated by commas.  Within JSON-LD, array order is not preserved by default, unless
      specific markup is provided (see <a href="#lists">Lists</a>). This is because the basic data model of JSON-LD
      is a directed <a class="tref" title="graph">graph</a>, which is inherently unordered.
    </dd>
    <dt><dfn title="string" id="dfn-string">string</dfn></dt><dd>
      A string is a sequence of zero or more Unicode characters, wrapped in double quotes, using backslash escapes. A
      character is represented as a single character string.
    </dd>
    <dt><dfn title="number" id="dfn-number">number</dfn></dt>
    <dd>
      A number is is similar to that used in most programming languages, except that the octal and hexadecimal formats are not used and that leading zeros are not allowed.</dd>
    <dt><dfn title="true" id="dfn-true">true</dfn> and <dfn title="false" id="dfn-false">false</dfn></dt><dd>
      Boolean values.
    </dd>
    <dt><dfn title="null" id="dfn-null">null</dfn></dt><dd>
      The use of the <em>null</em> value is undefined within JSON-LD.
      <div class="issue">Supporting <em>null</em> in JSON-LD might have a number of advantages and should be evaluated. This is currently an <a href="https://github.com/json-ld/json-ld.org/issues/11">open issue</a>.</div>
    </dd>
  </dl>
<p></p>
</div>

<div id="contributing" class="section">
<h3><span class="secno">1.2 </span>Contributing</h3>

<p>There are a number of ways that one may participate in the development of
this specification:</p>

<ul>
<li>Technical discussion typically occurs on the public mailing list:
<a href="http://lists.w3.org/Archives/Public/public-linked-json/">public-linked-json@w3.org</a>
</li>

<li><a href="http://json-ld.org/minutes/">Public teleconferences</a> are held
on Tuesdays at 1500UTC on the second and fourth week of each month.
</li>

<li>Specification bugs and issues should be reported in the
<a href="https://github.com/json-ld/json-ld.org/issues">issue tracker</a>.</li>

<li><a href="https://github.com/json-ld/json-ld.org/tree/main/spec">Source code</a> for the
specification can be found on Github.</li>

<li>The <a href="http://webchat.freenode.net/?channels=#json-ld">#json-ld</a>
IRC channel is available for real-time discussion on irc.freenode.net.</li>
</ul>

</div>

</div>

<div id="the-application-programming-interface" class="section">

<!-- OddPage -->
<h2><span class="secno">2. </span>The Application Programming Interface</h2>

<p>This API provides a clean mechanism that enables developers to convert
JSON-LD data into a a variety of output formats that are easier to work with in
various programming languages. If a JSON-LD API is provided in a programming
environment, the entirety of the following API <em class="rfc2119" title="must">must</em> be implemented.
</p>

<div id="jsonldprocessor" class="section">
<h3><span class="secno">2.1 </span>JsonLdProcessor</h3>
<pre class="idl"><span class="idlInterface" id="idl-def-JsonLdProcessor">[<span class="extAttr">NoInterfaceObject</span>]
interface <span class="idlInterfaceID">JsonLdProcessor</span> {
<span class="idlMethod">    <span class="idlMethType"><a>object</a></span> <span class="idlMethName"><a href="#widl-JsonLdProcessor-expand-object-object-input-object-context">expand</a></span> (<span class="idlParam"><span class="idlParamType"><a>object</a></span> <span class="idlParamName">input</span></span>, <span class="idlParam">optional <span class="idlParamType"><a>object</a>?</span> <span class="idlParamName">context</span></span>) raises (<span class="idlRaises"><a>InvalidContext</a></span>);</span>
<span class="idlMethod">    <span class="idlMethType"><a>object</a></span> <span class="idlMethName"><a href="#widl-JsonLdProcessor-compact-object-object-input-object-context">compact</a></span> (<span class="idlParam"><span class="idlParamType"><a>object</a></span> <span class="idlParamName">input</span></span>, <span class="idlParam">optional <span class="idlParamType"><a>object</a>?</span> <span class="idlParamName">context</span></span>) raises (<span class="idlRaises"><a>InvalidContext</a></span>, <span class="idlRaises"><a>ProcessingError</a></span>);</span>
<span class="idlMethod">    <span class="idlMethType"><a>object</a></span> <span class="idlMethName"><a href="#widl-JsonLdProcessor-frame-object-object-input-object-frame-object-options">frame</a></span> (<span class="idlParam"><span class="idlParamType"><a>object</a></span> <span class="idlParamName">input</span></span>, <span class="idlParam"><span class="idlParamType"><a>object</a></span> <span class="idlParamName">frame</span></span>, <span class="idlParam"><span class="idlParamType"><a>object</a></span> <span class="idlParamName">options</span></span>) raises (<span class="idlRaises"><a>InvalidFrame</a></span>);</span>
<span class="idlMethod">    <span class="idlMethType"><a>object</a></span> <span class="idlMethName"><a href="#widl-JsonLdProcessor-normalize-object-object-input-object-context">normalize</a></span> (<span class="idlParam"><span class="idlParamType"><a>object</a></span> <span class="idlParamName">input</span></span>, <span class="idlParam">optional <span class="idlParamType"><a>object</a>?</span> <span class="idlParamName">context</span></span>) raises (<span class="idlRaises"><a>InvalidContext</a></span>);</span>
<span class="idlMethod">    <span class="idlMethType"><a>object</a></span> <span class="idlMethName"><a href="#widl-JsonLdProcessor-triples-object-object-input-JsonLdTripleCallback-tripleCallback-object-context">triples</a></span> (<span class="idlParam"><span class="idlParamType"><a>object</a></span> <span class="idlParamName">input</span></span>, <span class="idlParam"><span class="idlParamType"><a href="#idl-def-JsonLdTripleCallback" class="idlType"><code>JsonLdTripleCallback</code></a></span> <span class="idlParamName">tripleCallback</span></span>, <span class="idlParam">optional <span class="idlParamType"><a>object</a>?</span> <span class="idlParamName">context</span></span>) raises (<span class="idlRaises"><a>InvalidContext</a></span>);</span>
};</span>
</pre><div id="methods" class="section"><h4><span class="secno">2.1.1 </span>Methods</h4><dl class="methods"><dt id="widl-JsonLdProcessor-compact-object-object-input-object-context"><code>compact</code></dt><dd><a href="#compaction">Compacts</a> the given <code>input</code>
    according to the steps in the
    <a href="#compaction-algorithm">Compaction Algorithm</a>. The
    <code>input</code> <em class="rfc2119" title="must">must</em> be copied, compacted and returned if there are
    no errors. If the compaction fails, an appropirate exception <em class="rfc2119" title="must">must</em> be
    thrown.
  

    

    

  <table class="parameters"><tr><th>Parameter</th><th>Type</th><th>Nullable</th><th>Optional</th><th>Description</th></tr><tr><td class="prmName">input</td><td class="prmType"><code><a>object</a></code></td><td class="prmNullFalse">✘</td><td class="prmOptFalse">✘</td><td class="prmDesc">The JSON-LD object to perform compaction on.</td></tr><tr><td class="prmName">context</td><td class="prmType"><code><a>object</a></code></td><td class="prmNullTrue">✔</td><td class="prmOptTrue">✔</td><td class="prmDesc">The base context to use when compacting the <code>input</code>.</td></tr></table><table class="exceptions"><tr><th>Exception</th><th>Description</th></tr><tr><td class="excName"><a>InvalidContext</a></td><td class="excDesc"><table class="exceptionCodes"><tr><td class="excCodeName"><code>INVALID_SYNTAX</code></td><td class="excCodeDesc">A general syntax error was detected in the <code>@context</code>.
     For example, if a <code>@coerce</code> key maps to anything other than
     a string or an array of strings, this exception would be raised.</td></tr><tr><td class="excCodeName"><code>MULTIPLE_DATATYPES</code></td><td class="excCodeDesc">There is more than one target datatype specified for a single
     property in the list of coercion rules. This means that the processor
     does not know what the developer intended for the target datatype for a
     property.</td></tr></table></td></tr><tr><td class="excName"><a>ProcessingError</a></td><td class="excDesc"><table class="exceptionCodes"><tr><td class="excCodeName"><code>LOSSY_COMPACTION</code></td><td class="excCodeDesc">The compaction would lead to a loss of information, such as a
     <code>@language</code> value.</td></tr><tr><td class="excCodeName"><code>CONFLICTING_DATATYPES</code></td><td class="excCodeDesc">The target datatype specified in the coercion rule and the
     datatype for the typed literal do not match.</td></tr></table></td></tr></table><div><em>Return type: </em><code><a>object</a></code></div></dd><dt id="widl-JsonLdProcessor-expand-object-object-input-object-context"><code>expand</code></dt><dd><a href="#expansion">Expands</a> the given <code>input</code>
    according to the steps in the
    <a href="#expansion-algorithm">Expansion Algorithm</a>. The
    <code>input</code> <em class="rfc2119" title="must">must</em> be copied, expanded and returned if there are
    no errors. If the expansion fails, an appropriate exception <em class="rfc2119" title="must">must</em> be thrown.

    

    

  <table class="parameters"><tr><th>Parameter</th><th>Type</th><th>Nullable</th><th>Optional</th><th>Description</th></tr><tr><td class="prmName">input</td><td class="prmType"><code><a>object</a></code></td><td class="prmNullFalse">✘</td><td class="prmOptFalse">✘</td><td class="prmDesc">The JSON-LD object to copy and perform the expansion upon.</td></tr><tr><td class="prmName">context</td><td class="prmType"><code><a>object</a></code></td><td class="prmNullTrue">✔</td><td class="prmOptTrue">✔</td><td class="prmDesc">An external context to use additionally to the context embedded in <code>input</code> when expanding the <code>input</code>.</td></tr></table><table class="exceptions"><tr><th>Exception</th><th>Description</th></tr><tr><td class="excName"><a>InvalidContext</a></td><td class="excDesc"><table class="exceptionCodes"><tr><td class="excCodeName"><code>INVALID_SYNTAX</code></td><td class="excCodeDesc">A general syntax error was detected in the <code>@context</code>.
     For example, if a <code>@coerce</code> key maps to anything other than
     a string or an array of strings, this exception would be raised.</td></tr><tr><td class="excCodeName"><code>MULTIPLE_DATATYPES</code></td><td class="excCodeDesc">There is more than one target datatype specified for a single
     property in the list of coercion rules. This means that the processor
     does not know what the developer intended for the target datatype for a
     property.</td></tr></table></td></tr></table><div><em>Return type: </em><code><a>object</a></code></div></dd><dt id="widl-JsonLdProcessor-frame-object-object-input-object-frame-object-options"><code>frame</code></dt><dd><a href="#framing">Frames</a> the given <code>input</code>
    using the <code>frame</code> according to the steps in the
    <a href="#framing-algorithm">Framing Algorithm</a>. The
    <code>input</code> is used to build the framed output and is returned if
    there are no errors. If there are no matches for the frame,
    <code>null</code> <em class="rfc2119" title="must">must</em> be returned. Exceptions <em class="rfc2119" title="must">must</em> be thrown if there are
    errors.
  

    

  <table class="parameters"><tr><th>Parameter</th><th>Type</th><th>Nullable</th><th>Optional</th><th>Description</th></tr><tr><td class="prmName">input</td><td class="prmType"><code><a>object</a></code></td><td class="prmNullFalse">✘</td><td class="prmOptFalse">✘</td><td class="prmDesc">The JSON-LD object to perform framing on.</td></tr><tr><td class="prmName">frame</td><td class="prmType"><code><a>object</a></code></td><td class="prmNullFalse">✘</td><td class="prmOptFalse">✘</td><td class="prmDesc">The frame to use when re-arranging the data.</td></tr><tr><td class="prmName">options</td><td class="prmType"><code><a>object</a></code></td><td class="prmNullFalse">✘</td><td class="prmOptFalse">✘</td><td class="prmDesc">A set of options that will affect the framing algorithm.</td></tr></table><table class="exceptions"><tr><th>Exception</th><th>Description</th></tr><tr><td class="excName"><a>InvalidFrame</a></td><td class="excDesc"><table class="exceptionCodes"><tr><td class="excCodeName"><code>INVALID_SYNTAX</code></td><td class="excCodeDesc">A frame must be either an object or an array of objects, if the frame
    is neither of these types, this exception is thrown.</td></tr><tr><td class="excCodeName"><code>MULTIPLE_EMBEDS</code></td><td class="excCodeDesc">A subject IRI was specified in more than one place in the input
    frame. More than one embed of a given subject IRI is not allowed, and if
    requested, <em class="rfc2119" title="must">must</em> result in this exception.</td></tr></table></td></tr></table><div><em>Return type: </em><code><a>object</a></code></div></dd><dt id="widl-JsonLdProcessor-normalize-object-object-input-object-context"><code>normalize</code></dt><dd><a href="#normalization">Normalizes</a> the given <code>input</code>
    according to the steps in the
    <a href="#normalization-algorithm">Normalization Algorithm</a>. The
    <code>input</code> <em class="rfc2119" title="must">must</em> be copied, normalized and returned if there are
    no errors. If the compaction fails, <code>null</code> <em class="rfc2119" title="must">must</em> be returned.
  

    

  <table class="parameters"><tr><th>Parameter</th><th>Type</th><th>Nullable</th><th>Optional</th><th>Description</th></tr><tr><td class="prmName">input</td><td class="prmType"><code><a>object</a></code></td><td class="prmNullFalse">✘</td><td class="prmOptFalse">✘</td><td class="prmDesc">The JSON-LD object to perform normalization upon.</td></tr><tr><td class="prmName">context</td><td class="prmType"><code><a>object</a></code></td><td class="prmNullTrue">✔</td><td class="prmOptTrue">✔</td><td class="prmDesc">An external context to use additionally to the context embedded in <code>input</code> when expanding the <code>input</code>.</td></tr></table><table class="exceptions"><tr><th>Exception</th><th>Description</th></tr><tr><td class="excName"><a>InvalidContext</a></td><td class="excDesc"><table class="exceptionCodes"><tr><td class="excCodeName"><code>INVALID_SYNTAX</code></td><td class="excCodeDesc">A general syntax error was detected in the <code>@context</code>.
     For example, if a <code>@coerce</code> key maps to anything other than
     a string or an array of strings, this exception would be raised.</td></tr><tr><td class="excCodeName"><code>MULTIPLE_DATATYPES</code></td><td class="excCodeDesc">There is more than one target datatype specified for a single
     property in the list of coercion rules. This means that the processor
     does not know what the developer intended for the target datatype for a
     property.</td></tr></table></td></tr></table><div><em>Return type: </em><code><a>object</a></code></div></dd><dt id="widl-JsonLdProcessor-triples-object-object-input-JsonLdTripleCallback-tripleCallback-object-context"><code>triples</code></dt><dd>Processes the <code>input</code> according to the
    <a href="#rdf-conversion-algorithm">RDF Conversion Algorithm</a>, calling
    the provided <code>tripleCallback</code> for each triple generated.
  

    

  <table class="parameters"><tr><th>Parameter</th><th>Type</th><th>Nullable</th><th>Optional</th><th>Description</th></tr><tr><td class="prmName">input</td><td class="prmType"><code><a>object</a></code></td><td class="prmNullFalse">✘</td><td class="prmOptFalse">✘</td><td class="prmDesc">The JSON-LD object to process when outputting triples.</td></tr><tr><td class="prmName">tripleCallback</td><td class="prmType"><code><a href="#idl-def-JsonLdTripleCallback" class="idlType"><code>JsonLdTripleCallback</code></a></code></td><td class="prmNullFalse">✘</td><td class="prmOptFalse">✘</td><td class="prmDesc">A callback that is called whenever a processing error occurs on
     the given <code>input</code>.
     <div class="issue">This callback should be aligned with the
       RDF API.</div></td></tr><tr><td class="prmName">context</td><td class="prmType"><code><a>object</a></code></td><td class="prmNullTrue">✔</td><td class="prmOptTrue">✔</td><td class="prmDesc">An external context to use additionally to the context embedded in <code>input</code> when expanding the <code>input</code>.</td></tr></table><table class="exceptions"><tr><th>Exception</th><th>Description</th></tr><tr><td class="excName"><a>InvalidContext</a></td><td class="excDesc"><table class="exceptionCodes"><tr><td class="excCodeName"><code>INVALID_SYNTAX</code></td><td class="excCodeDesc">A general syntax error was detected in the <code>@context</code>.
     For example, if a <code>@coerce</code> key maps to anything other than
     a string or an array of strings, this exception would be raised.</td></tr><tr><td class="excCodeName"><code>MULTIPLE_DATATYPES</code></td><td class="excCodeDesc">There is more than one target datatype specified for a single
     property in the list of coercion rules. This means that the processor
     does not know what the developer intended for the target datatype for a
     property.</td></tr></table></td></tr></table><div><em>Return type: </em><code><a>object</a></code></div></dd></dl></div>

</div>

<div id="jsonldtriplecallback" class="section">
<h3><span class="secno">2.2 </span>JsonLdTripleCallback</h3>
<p>The JsonLdTripleCallback is called whenever the processor generates a
triple during the <code>triple()</code> call.</p>

<pre class="idl"><span class="idlInterface" id="idl-def-JsonLdTripleCallback">[<span class="extAttr">NoInterfaceObject Callback</span>]
interface <span class="idlInterfaceID">JsonLdTripleCallback</span> {
<span class="idlMethod">    <span class="idlMethType"><a>void</a></span> <span class="idlMethName"><a href="#widl-JsonLdTripleCallback-triple-void-DOMString-subject-DOMString-property-DOMString-objectType-DOMString-object-DOMString-datatype-DOMString-language">triple</a></span> (<span class="idlParam"><span class="idlParamType"><a>DOMString</a></span> <span class="idlParamName">subject</span></span>, <span class="idlParam"><span class="idlParamType"><a>DOMString</a></span> <span class="idlParamName">property</span></span>, <span class="idlParam"><span class="idlParamType"><a>DOMString</a></span> <span class="idlParamName">objectType</span></span>, <span class="idlParam"><span class="idlParamType"><a>DOMString</a></span> <span class="idlParamName">object</span></span>, <span class="idlParam"><span class="idlParamType"><a>DOMString</a>?</span> <span class="idlParamName">datatype</span></span>, <span class="idlParam"><span class="idlParamType"><a>DOMString</a>?</span> <span class="idlParamName">language</span></span>);</span>
};</span>
</pre><div id="methods-1" class="section"><h4><span class="secno">2.2.1 </span>Methods</h4><dl class="methods"><dt id="widl-JsonLdTripleCallback-triple-void-DOMString-subject-DOMString-property-DOMString-objectType-DOMString-object-DOMString-datatype-DOMString-language"><code>triple</code></dt><dd>This callback is invoked whenever a triple is generated by the processor.
  
  <table class="parameters"><tr><th>Parameter</th><th>Type</th><th>Nullable</th><th>Optional</th><th>Description</th></tr><tr><td class="prmName">subject</td><td class="prmType"><code><a>DOMString</a></code></td><td class="prmNullFalse">✘</td><td class="prmOptFalse">✘</td><td class="prmDesc">The subject IRI that is associated with the triple.</td></tr><tr><td class="prmName">property</td><td class="prmType"><code><a>DOMString</a></code></td><td class="prmNullFalse">✘</td><td class="prmOptFalse">✘</td><td class="prmDesc">The property IRI that is associated with the triple.</td></tr><tr><td class="prmName">objectType</td><td class="prmType"><code><a>DOMString</a></code></td><td class="prmNullFalse">✘</td><td class="prmOptFalse">✘</td><td class="prmDesc">The type of object that is associated with the triple. Valid values
       are <code>IRI</code> and <code>literal</code>.</td></tr><tr><td class="prmName">object</td><td class="prmType"><code><a>DOMString</a></code></td><td class="prmNullFalse">✘</td><td class="prmOptFalse">✘</td><td class="prmDesc">The object value associated with the subject and the property.</td></tr><tr><td class="prmName">datatype</td><td class="prmType"><code><a>DOMString</a></code></td><td class="prmNullTrue">✔</td><td class="prmOptFalse">✘</td><td class="prmDesc">The datatype associated with the object.</td></tr><tr><td class="prmName">language</td><td class="prmType"><code><a>DOMString</a></code></td><td class="prmNullTrue">✔</td><td class="prmOptFalse">✘</td><td class="prmDesc">The language associated with the object in BCP47 format.</td></tr></table><div><em>No exceptions.</em></div><div><em>Return type: </em><code><a>void</a></code></div></dd></dl></div>
</div>


</div>

<div id="algorithms" class="section">

<!-- OddPage -->
<h2><span class="secno">3. </span>Algorithms</h2>

<p>All algorithms described in this section are intended to operate on
language-native data structures. That is, the serialization to a text-based
JSON document isn't required as input or output to any of these algorithms and
language-native data structures <em class="rfc2119" title="must">must</em> be used where applicable.</p>

<div id="syntax-tokens-and-keywords" class="section">
  <h3><span class="secno">3.1 </span>Syntax Tokens and Keywords</h3>

  <p>JSON-LD specifies a number of syntax tokens and keywords that are using
  in all algorithms described in this section:</p>

  <dl>
  <dt><code>@context</code></dt><dd>Used to set the <a class="tref internalDFN" title="local_context" href="#dfn-local_context">local context</a>.</dd>
  <dt><code>@base</code></dt><dd>Used to set the base IRI for all object IRIs affected  by the <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a>.</dd>
  <dt><code>@vocab</code></dt><dd>Used to set the base IRI for all property IRIs affected by the <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a>.</dd>
  <dt><code>@coerce</code></dt><dd>Used to specify type coercion rules.</dd>
  <dt><code>@literal</code></dt><dd>Used to specify a literal value.</dd>
  <dt><code>@iri</code></dt><dd>Used to specify an IRI value.</dd>
  <dt><code>@language</code></dt><dd>Used to specify the language for a literal.</dd>
  <dt><code>@datatype</code></dt><dd>Used to specify the datatype for a literal.</dd>
  <dt><code>:</code></dt><dd>The separator for JSON keys and values that use the <a class="tref" title="prefix">prefix</a> mechanism.</dd>
  <dt><code>@subject</code></dt><dd>Sets the active subject.</dd>
  <dt><code>@type</code></dt><dd>Used to set the type of the active subject.</dd>
  </dl>
</div>

<div id="algorithm-terms" class="section">
  <h3><span class="secno">3.2 </span>Algorithm Terms</h3>
  <dl>
    <dt><dfn title="initial_context" id="dfn-initial_context">initial context</dfn></dt>
    <dd>
      a context that is specified to the algorithm before processing begins.
    </dd>
    <dt><dfn title="active_subject" id="dfn-active_subject">active subject</dfn></dt>
    <dd>
      the currently active subject that the processor should use when
      processing.
    </dd>
    <dt><dfn title="active_property" id="dfn-active_property">active property</dfn></dt>
    <dd>
      the currently active property that the processor should use when
      processing.
    </dd>
    <dt><dfn title="active_object" id="dfn-active_object">active object</dfn></dt>
    <dd>
      the currently active object that the processor should use when
      processing.
    </dd>
    <dt><dfn title="active_context" id="dfn-active_context">active context</dfn></dt>
    <dd>
      a context that is used to resolve <a class="tref" title="prefix">prefix</a>es and
      <a class="tref" title="term">term</a>s while the processing
      algorithm is running. The <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a> is the context
      contained within the <a class="tref internalDFN" title="processor_state" href="#dfn-processor_state">processor state</a>.
    </dd>
    <dt><dfn title="local_context" id="dfn-local_context">local context</dfn></dt>
    <dd>
      a context that is specified within a <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a>,
      specified via the <code>@context</code> keyword.
    </dd>
    <dt><dfn title="processor_state" id="dfn-processor_state">processor state</dfn></dt>
    <dd>
      the <a class="tref internalDFN" title="processor_state" href="#dfn-processor_state">processor state</a>, which includes the <a class="tref" title="active__context">active
      context</a>, <a class="tref" title="current_subject">current subject</a>, and
      <a class="tref" title="current_property">current property</a>. The <a class="tref internalDFN" title="processor_state" href="#dfn-processor_state">processor state</a> is managed
      as a stack with elements from the previous <a class="tref internalDFN" title="processor_state" href="#dfn-processor_state">processor state</a>
      copied into a new <a class="tref internalDFN" title="processor_state" href="#dfn-processor_state">processor state</a> when entering a new
      <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a>.
    </dd>
    <dt><dfn title="JSON-LD_input" id="dfn-json-ld_input">JSON-LD input</dfn></dt>
    <dd>
      The JSON-LD data structure that is provided as input to the algorithm.
    </dd>
    <dt><dfn title="JSON-LD_output" id="dfn-json-ld_output">JSON-LD output</dfn></dt>
    <dd>
      The JSON-LD data structure that is produced as output by the algorithm.
    </dd>

  </dl>
</div>

<div id="context-1" class="section">
  <h3 id="context"><span class="secno">3.3 </span>Context</h3>
  <p>
    Processing of JSON-LD data structure is managed recursively.
    During processing, each rule is applied using information provided by the <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a>.
    Processing begins by pushing a new <a class="tref internalDFN" title="processor_state" href="#dfn-processor_state">processor state</a> onto the <a class="tref internalDFN" title="processor_state" href="#dfn-processor_state">processor state</a> stack and
    initializing the <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a> with the <a class="tref internalDFN" title="initial_context" href="#dfn-initial_context">initial context</a>. If a <a class="tref internalDFN" title="local_context" href="#dfn-local_context">local context</a> is encountered,
    information from the <a class="tref internalDFN" title="local_context" href="#dfn-local_context">local context</a> is merged into the <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a>.
  </p>
  <p>
    The <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a> is used for expanding keys and values of a <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> (or elements
    of a list (see <span a="#list-processing">List Processing</span>)).
  </p>
  <p>
    A <a class="tref internalDFN" title="local_context" href="#dfn-local_context">local context</a> is identified within a <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> having a key of
    <code>@context</code> with <a class="tref internalDFN" title="string" href="#dfn-string">string</a> or a <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> value. When processing a <a class="tref" title="local__context">local
    context</a>, special processing rules apply:
  </p>
  <ol class="algorithm">
    <li>Create a new, empty <a class="tref internalDFN" title="local_context" href="#dfn-local_context">local context</a>.</li>
    <li>
      If the value is a simple <a class="tref internalDFN" title="string" href="#dfn-string">string</a>, it <em class="rfc2119" title="must">must</em> have a lexical form of IRI and used to initialize
      a new JSON document which replaces the value for subsequent processing.
    </li>
    <li>If the value is a <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a>, perform the following steps:
      <ol class="algorithm">
        <li>
          If the <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> has a <code>@base</code> key, it <em class="rfc2119" title="must">must</em> have a value of a simple
          <a class="tref internalDFN" title="string" href="#dfn-string">string</a> with the lexical form of an absolute IRI. Add the base mapping to the <a class="tref" title="local__context">local
          context</a>. <p class="issue">Turtle allows @base to be relative. If we did this, we
          would have to add <a href="#iri-expansion">IRI Expansion</a>.</p>
        </li>
        <li>
          If the <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> has a <code>@vocab</code> key, it <em class="rfc2119" title="must">must</em> have a value of a simple
          <a class="tref internalDFN" title="string" href="#dfn-string">string</a> with the lexical form of an absolute IRI. Add the vocabulary mapping to the
          <a class="tref internalDFN" title="local_context" href="#dfn-local_context">local context</a> after performing <a href="#iri-expansion">IRI Expansion</a> on
          the associated value.
        </li>
        <li>
          If the <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> has a <code>@coerce</code> key, it <em class="rfc2119" title="must">must</em> have a value of a
          <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a>. Add the <code>@coerce</code> mapping to the <a class="tref internalDFN" title="local_context" href="#dfn-local_context">local context</a>
          performing <a href="#iri-expansion">IRI Expansion</a> on the associated value(s).
        </li>
        <li>
          Otherwise, the key <em class="rfc2119" title="must">must</em> have the lexical form of <cite><a href="http://www.w3.org/TR/2009/REC-xml-names-20091208/#NT-NCName">NCName</a></cite> and
          <em class="rfc2119" title="must">must</em> have the value of a simple <a class="tref internalDFN" title="string" href="#dfn-string">string</a> with the lexical form of IRI. Merge the key-value
          pair into the <a class="tref internalDFN" title="local_context" href="#dfn-local_context">local context</a>.
        </li>
      </ol>
    </li>
    <li>
      Merge the of <a class="tref internalDFN" title="local_context" href="#dfn-local_context">local context</a>'s <code>@coerce</code> mapping into  the
      <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a>'s <code>@coerce</code> mapping as described <a href="#coerce">below</a>.
    </li>
    <li>
      Merge all entries other than the <code>@coerce</code> mapping from the <a class="tref internalDFN" title="local_context" href="#dfn-local_context">local context</a> to the
      <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a> overwriting any duplicate values.
    </li>
  </ol>

  <div id="coerce" class="section">
    <h4><span class="secno">3.3.1 </span>Coerce</h4>
    <p>
      Map each key-value pair in the <a class="tref internalDFN" title="local_context" href="#dfn-local_context">local context</a>'s
      <code>@coerce</code> mapping into the <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a>'s
      <code>@coerce</code> mapping, overwriting any duplicate values in
      the <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a>'s <code>@coerce</code> mapping.
      The <code>@coerce</code> mapping has either a single
      <code>prefix:term</code> value, a single <a class="tref" title="term">term</a> value or an
      <a class="tref internalDFN" title="array" href="#dfn-array">array</a> of <code>prefix:term</code> or <a class="tref" title="term">term</a> values.
      When merging with an existing mapping in the <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a>,
      map all <a class="tref" title="prefix">prefix</a> and <a class="tref" title="term">term</a> values to
      <a class="tref internalDFN" title="array" href="#dfn-array">array</a> form and replace with the union of the value from
      the <a class="tref internalDFN" title="local_context" href="#dfn-local_context">local context</a> and the value of the
      <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a>. If the result is an <a class="tref internalDFN" title="array" href="#dfn-array">array</a>
      with a single value, the processor <em class="rfc2119" title="may">may</em> represent this as a string value.
    </p>
  </div>

  <div id="initial-context" class="section">
    <h4><span class="secno">3.3.2 </span>Initial Context</h4>
    <p>The <a class="tref internalDFN" title="initial_context" href="#dfn-initial_context">initial context</a> is initialized as follows:</p>
    <ul>
      <li>
        <code>@base</code> is set using <cite><href="http: www.ietf.org="" rfc="" rfc2396.txt"="">section 5.1 Establishing a
        Base URI</href="http:></cite> of [<cite><a class="bibref" rel="biblioentry" href="#bib-RFC3986">RFC3986</a></cite>]. Processors <em class="rfc2119" title="may">may</em> provide a means
        of setting the base IRI programatically.
      </li>
      <li><code>@coerce</code> is set with a single mapping from <code>@iri</code> to <code>@type</code>.</li>
    </ul>
    <pre class="example">{
    &quot;@base&quot;: <span class="diff">document-location</span>,
    &quot;@coerce&quot;: {
      &quot;@iri&quot;: &quot;@type&quot;
    }
}</pre>
  </div>
</div>

<div id="iri-expansion" class="section">
  <h3><span class="secno">3.4 </span>IRI Expansion</h3>
  <p>Keys and some values are evaluated to produce an IRI. This section defines an algorithm for
    transforming a value representing an IRI into an actual IRI.</p>
  <p>IRIs may be represented as an absolute IRI, a <a class="tref" title="term">term</a>, a <a class="tref" title="prefix">prefix</a>:<a class="tref" title="term">term</a> construct, or as a value relative to <code>@base</code>
    or <code>@vocab</code>.</p>
  <p>The algorithm for generating an IRI is:
    </p><ol class="algorithm">
      <li>Split the value into a <em>prefix</em> and <em>suffix</em> from the first occurrence of ':'.</li>
      <li>If the prefix is a '_' (underscore), the IRI is unchanged.</li>
      <li>If the <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a> contains a mapping for <em>prefix</em>, generate an IRI
        by prepending the mapped prefix to the (possibly empty) suffix using textual concatenation. Note that an empty
        suffix and no suffix (meaning the value contains no ':' string at all) are treated equivalently.</li>
      <li>If the IRI being processed is for a property (i.e., a key's value in a <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a>, or a
        value in a <code>@coerce</code> mapping) and the active context has a <code>@vocab</code> mapping,
        join the mapped value to the suffix using textual concatenation.</li>
      <li>If the IRI being processed is for a subject or object (i.e., not a property) and the active context has a <code>@base</code> mapping,
        join the mapped value to the suffix using the method described in [<cite><a class="bibref" rel="biblioentry" href="#bib-RFC3986">RFC3986</a></cite>].</li>
      <li>Otherwise, use the value directly as an IRI.</li>
    </ol>
  <p></p>
</div>

<div id="iri-compaction" class="section">
  <h3><span class="secno">3.5 </span>IRI Compaction</h3>
  <p>Some keys and values are expressed using IRIs. This section defines an
    algorithm for transforming an IRI to a compact IRI using the
    <a class="tref" title="term">term</a>s and <a class="tref" title="prefix">prefix</a>es specified in the
    <a class="tref internalDFN" title="local_context" href="#dfn-local_context">local context</a>.</p>

  <p>The algorithm for generating a compacted IRI is:
    </p><ol class="algorithm">
      <li>Search every key-value pair in the <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a> for
        a <a class="tref" title="term">term</a> that is a complete match
        against the IRI. If a complete match is found, the resulting compacted
        IRI is the <a class="tref" title="term">term</a> associated with the IRI in the
        <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a>.</li>
      <li>If a complete match is not found, search for a partial match from
        the beginning of the IRI. For all matches that are found, the resulting
        compacted IRI is the <a class="tref" title="prefix">prefix</a> associated with the partially
        matched IRI in the <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a> concatenated with a
        colon (:) character and the unmatched part of the string. If there is
        more than one compacted IRI produced, the final value is the
        shortest and lexicographically least value of the entire set of compacted IRIs.</li>
    </ol>
  <p></p>
</div>

<div id="value-expansion" class="section">
  <h3><span class="secno">3.6 </span>Value Expansion</h3>
  <p>Some values in JSON-LD can be expressed in a compact form. These values
    are required to be expanded at times when processing JSON-LD documents.
  </p>

  <p>The algorithm for expanding a value is:
    </p><ol class="algorithm">
      <li>If the key that is associated with the value has an associated
        coercion entry in the <a class="tref internalDFN" title="local_context" href="#dfn-local_context">local context</a>, the resulting
        expansion is an object populated according to the following steps:
        <ol class="algorithm">
          <li>If the coercion target is <code>@iri</code>, expand the value
            by adding a new key-value pair where the key is <code>@iri</code>
            and the value is the expanded IRI according to the
            <a href="#iri-expansion">IRI Expansion</a> rules.</li>
          <li>If the coercion target is a typed literal, expand the value
            by adding two new key-value pairs. The first key-value pair
            will be <code>@literal</code> and the unexpanded value. The second
            key-value pair will be <code>@datatype</code> and the associated
            coercion datatype expanded according to the
            <a href="#iri-expansion">IRI Expansion</a> rules.</li>
        </ol>
      </li>
    </ol>
  <p></p>
</div>

<div id="value-compaction" class="section">
  <h3><span class="secno">3.7 </span>Value Compaction</h3>
  <p>Some values, such as IRIs and typed literals, may be expressed in an
    expanded form in JSON-LD. These values are required to be compacted at
    times when processing JSON-LD documents.
  </p>

  <p>The algorithm for compacting a value is:
    </p><ol class="algorithm">
      <li>If the <a class="tref internalDFN" title="local_context" href="#dfn-local_context">local context</a> contains a coercion target for the
        key that is associated with the value, compact the value using the
        following steps:
        <ol class="algorithm">
          <li>If the coercion target is an <code>@iri</code>, the compacted
            value is the value associated with the <code>@iri</code> key,
            processed according to the
            <a href="#iri-compaction">IRI Compaction</a> steps.</li>
          <li>If the coercion target is a typed literal, the compacted
            value is the value associated with the <code>@literal</code> key.
          </li>
          <li>Otherwise, the value is not modified.</li>
        </ol>
      </li>
    </ol>
  <p></p>
</div>

<div id="expansion" class="section">
<h3><span class="secno">3.8 </span>Expansion</h3>

<p class="issue">This algorithm is a work in progress, do not implement it.</p>

<p>As stated previously, expansion is the process of taking a JSON-LD
input and expanding all IRIs and typed literals to their fully-expanded form.
The output will not contain a single context declaration and will have all IRIs
and typed literals fully expanded.
</p>

<div id="expansion-algorithm" class="section">
<h4><span class="secno">3.8.1 </span>Expansion Algorithm</h4>

<ol class="algorithm">
  <li>If the top-level item in the <a class="tref internalDFN" title="JSON-LD_input" href="#dfn-json-ld_input">JSON-LD input</a> is an <a class="tref internalDFN" title="array" href="#dfn-array">array</a>,
  process each item in the <a class="tref internalDFN" title="array" href="#dfn-array">array</a> recursively using this algorithm.</li>
  <li>If the top-level item in the <a class="tref internalDFN" title="JSON-LD_input" href="#dfn-json-ld_input">JSON-LD input</a> is an object,
  update the <a class="tref internalDFN" title="local_context" href="#dfn-local_context">local context</a> according to the steps outlined in
  the <a href="#context">context</a> section. Process each key, expanding
  the key according to the <a href="#iri-expansion">IRI Expansion</a> rules.</li>
  <ol class="algorithm">
    <li>Process each value associated with each key:
      <ol class="algorithm">
        <li>If the value is an <a class="tref internalDFN" title="array" href="#dfn-array">array</a>, process each item in the <a class="tref internalDFN" title="array" href="#dfn-array">array</a>
        recursively using this algorithm.</li>
        <li>If the value is an object, process the object recursively
        using this algorithm.</li>
        <li>Otherwise, check to see the associated key has an associated
        coercion rule. If the value should be coerced, expand the value
        according to the <a href="#value-expansion">Value Expansion</a> rules.
        If the value does not need to be coerced, leave the value as-is.
        </li>
      </ol>
    </li><li>Remove the context from the object.</li>
  </ol>
</ol>
</div>

</div>

<div id="compaction" class="section">
<h3><span class="secno">3.9 </span>Compaction</h3>

<p class="issue">This algorithm is a work in progress, do not implement it.</p>

<p>As stated previously, compaction is the process of taking a JSON-LD
input and compacting all IRIs using a given context. The output
will contain a single top-level context declaration and will only use
<a class="tref" title="term">term</a>s and <a class="tref" title="prefix">prefix</a>es and will ensure that all
typed literals are fully compacted.
</p>

<div id="compaction-algorithm" class="section">
<h4><span class="secno">3.9.1 </span>Compaction Algorithm</h4>

<ol class="algorithm">
  <li>Perform the <a href="#expansion-algorithm">Expansion Algorithm</a> on
  the <a class="tref internalDFN" title="JSON-LD_input" href="#dfn-json-ld_input">JSON-LD input</a>. This removes any existing context to allow the given context to be cleanly applied.</li>
  <li>Set the <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a> to the given context.
  </li><li>If the top-level item is an <a class="tref internalDFN" title="array" href="#dfn-array">array</a>, process each item in the <a class="tref internalDFN" title="array" href="#dfn-array">array</a>
    recursively, starting at this step.
  </li><li>If the top-level item is an object, compress each key using the steps
    defined in <a href="#iri-compaction">IRI Compaction</a> and compress each
    value using the steps defined in
    <a href="#value-compaction">Value Compaction</a>.</li>
  
</ol>
</div>

</div>


<div id="framing" class="section">
<h3><span class="secno">3.10 </span>Framing</h3>

<p class="issue">This algorithm is a work in progress, do not implement it.</p>

<p>A JSON-LD document is a representation of a directed graph. A single
directed graph can have many different serializations, each expressing
exactly the same information. Developers typically don't work directly with
graphs, but rather, prefer trees when dealing with JSON. While mapping a graph
to a tree can be done, the layout of the end result must be specified in
advance. This section defines an algorithm for mapping a graph to
a tree given a <a class="tref" title="frame">frame</a>.
</p>

<div id="framing-algorithm-terms" class="section">
<h4><span class="secno">3.10.1 </span>Framing Algorithm Terms</h4>
 <dl>
   <dt><dfn title="input_frame" id="dfn-input_frame">input frame</dfn></dt>
   <dd>
     the initial <a class="tref" title="frame">frame</a> provided to the framing algorithm.
   </dd>
   <dt><dfn title="framing_context" id="dfn-framing_context">framing context</dfn></dt>
   <dd>
     a context containing the <a class="tref internalDFN" title="object_embed_flag" href="#dfn-object_embed_flag">object embed flag</a>, the
     <a class="tref internalDFN" title="explicit_inclusion_flag" href="#dfn-explicit_inclusion_flag">explicit inclusion flag</a> and the
     <a class="tref" title="omit_default_flag">omit default flag</a>.
   </dd>
   <dt><dfn title="object_embed_flag" id="dfn-object_embed_flag">object embed flag</dfn></dt>
   <dd>
     a flag specifying that objects should be directly embedded in the output,
     instead of being referred to by their IRI.
   </dd>
   <dt><dfn title="explicit_inclusion_flag" id="dfn-explicit_inclusion_flag">explicit inclusion flag</dfn></dt>
   <dd>
     a flag specifying that for properties to be included in the output, they
     must be explicitly declared in the <a class="tref internalDFN" title="framing_context" href="#dfn-framing_context">framing context</a>.
   </dd>
   <dt><dfn title="omit_missing_properties_flag" id="dfn-omit_missing_properties_flag">omit missing properties flag</dfn></dt>
   <dd>
     a flag specifying that properties that are missing from the
     <a class="tref internalDFN" title="JSON-LD_input" href="#dfn-json-ld_input">JSON-LD input</a> should be omitted from the output.
   </dd>
   <dt><dfn title="match_limit" id="dfn-match_limit">match limit</dfn></dt>
   <dd>
     A value specifying the maximum number of matches to accept when building
     arrays of values during the framing algorithm. A value of -1 specifies
     that there is no match limit.
   </dd>
   <dt><dfn title="map_of_embedded_subjects" id="dfn-map_of_embedded_subjects">map of embedded subjects</dfn></dt>
   <dd>
     A map that tracks if a subject has been embedded in the output of the
     <a href="#framing-algorithm">Framing Algorithm</a>.
   </dd>
 </dl>
</div>

<div id="framing-algorithm" class="section">
<h4><span class="secno">3.10.2 </span>Framing Algorithm</h4>

<p>The framing algorithm takes <a class="tref internalDFN" title="JSON-LD_input" href="#dfn-json-ld_input">JSON-LD input</a> that has been
normalized according to the
<a href="#normalization-algorithm">Normalization Algorithm</a>
(<strong>normalized input</strong>), an
<a class="tref internalDFN" title="input_frame" href="#dfn-input_frame">input frame</a> that has been expanded according to the
<a href="#expansion-algorithm">Expansion Algorithm</a>
(<strong>expanded frame</strong>), and a number of options and produces
<a class="tref internalDFN" title="JSON-LD_output" href="#dfn-json-ld_output">JSON-LD output</a>. The following series of steps is the recursive
portion of the framing algorithm:
</p>

<ol class="algorithm">
  <li>Initialize the <a class="tref internalDFN" title="framing_context" href="#dfn-framing_context">framing context</a> by setting the
   <a class="tref internalDFN" title="object_embed_flag" href="#dfn-object_embed_flag">object embed flag</a>, clearing the
   <a class="tref internalDFN" title="explicit_inclusion_flag" href="#dfn-explicit_inclusion_flag">explicit inclusion flag</a>, and clearing the
   <a class="tref internalDFN" title="omit_missing_properties_flag" href="#dfn-omit_missing_properties_flag">omit missing properties flag</a>. Override these values
   based on input options provided to the algorithm by the application.
  </li>
  <li>Generate a <dfn title="list_of_frames" id="dfn-list_of_frames">list of frames</dfn> by processing the
    <strong>expanded frame</strong>:
    <ol class="algorithm">
      <li>If the <strong>expanded frame</strong> is not an <a class="tref internalDFN" title="array" href="#dfn-array">array</a>, set
        <a class="tref internalDFN" title="match_limit" href="#dfn-match_limit">match limit</a> to 1, place the
        <strong>expanded frame</strong> into the <a class="tref internalDFN" title="list_of_frames" href="#dfn-list_of_frames">list of frames</a>,
        and set the <a class="tref internalDFN" title="JSON-LD_output" href="#dfn-json-ld_output">JSON-LD output</a> to <code>null</code>.</li>
      <li>If the <strong>expanded frame</strong> is an empty <a class="tref internalDFN" title="array" href="#dfn-array">array</a>, place an
        empty object into the <a class="tref internalDFN" title="list_of_frames" href="#dfn-list_of_frames">list of frames</a>,
        set the <a class="tref internalDFN" title="JSON-LD_output" href="#dfn-json-ld_output">JSON-LD output</a> to an <a class="tref internalDFN" title="array" href="#dfn-array">array</a>, and set
        <a class="tref internalDFN" title="match_limit" href="#dfn-match_limit">match limit</a> to -1.</li>
      <li>If the <strong>expanded frame</strong> is a non-empty <a class="tref internalDFN" title="array" href="#dfn-array">array</a>, add
        each item in the <strong>expanded frame</strong> into the
        <a class="tref internalDFN" title="list_of_frames" href="#dfn-list_of_frames">list of frames</a>, set the <a class="tref internalDFN" title="JSON-LD_output" href="#dfn-json-ld_output">JSON-LD output</a> to an
        <a class="tref internalDFN" title="array" href="#dfn-array">array</a>, and set <a class="tref internalDFN" title="match_limit" href="#dfn-match_limit">match limit</a> to -1.</li>
    </ol></li>
  <li>Create a <dfn title="match_array" id="dfn-match_array">match array</dfn> for each <strong>expanded frame</strong>
    in the <a class="tref internalDFN" title="list_of_frames" href="#dfn-list_of_frames">list of frames</a> halting when either the
    <a class="tref internalDFN" title="match_limit" href="#dfn-match_limit">match limit</a> is zero or the end of the
    <a class="tref internalDFN" title="list_of_frames" href="#dfn-list_of_frames">list of frames</a> is reached. If an
    <strong>expanded frame</strong> is
    not an object, the processor <em class="rfc2119" title="must">must</em> throw a <code>Invalid Frame Format</code>
    exception. Add each matching item from the <strong>normalized input</strong>
    to the <a class="tref" title="matches_array">matches array</a> and decrement the
    <a class="tref internalDFN" title="match_limit" href="#dfn-match_limit">match limit</a> by 1 if:
    <ol class="algorithm">
       <li>The <strong>expanded frame</strong> has an <code>rdf:type</code>
         that exists in the item's list of <code>rdf:type</code>s. Note:
         the <code>rdf:type</code> can be an <a class="tref internalDFN" title="array" href="#dfn-array">array</a>, but only one value needs
         to be in common between the item and the
         <strong>expanded frame</strong> for a match.</li>
       <li>The <strong>expanded frame</strong> does not have an
         <code>rdf:type</code> property, but every property in the
         <strong>expanded frame</strong> exists in the item.</li>
    </ol></li>
  <li>Process each item in the <a class="tref internalDFN" title="match_array" href="#dfn-match_array">match array</a> with its associated
    <dfn title="match_frame" id="dfn-match_frame">match frame</dfn>:
    <ol class="algorithm">
      <li>If the <a class="tref internalDFN" title="match_frame" href="#dfn-match_frame">match frame</a> contains an <code>@embed</code>
        keyword, set the <a class="tref internalDFN" title="object_embed_flag" href="#dfn-object_embed_flag">object embed flag</a> to its value.
        If the <a class="tref internalDFN" title="match_frame" href="#dfn-match_frame">match frame</a> contains an <code>@explicit</code>
        keyword, set the <a class="tref internalDFN" title="explicit_inclusion_flag" href="#dfn-explicit_inclusion_flag">explicit inclusion flag</a> to its value.
        Note: if the keyword exists, but the value is neither
        <code>true</code> or <code>false</code>, set the associated flag to
        <code>true</code>.</li>
      <li>If the <a class="tref internalDFN" title="object_embed_flag" href="#dfn-object_embed_flag">object embed flag</a> is cleared and the item has
        the <code>@subject</code> property, replace the item with the value
        of the <code>@subject</code> property.</li>
      <li>If the <a class="tref internalDFN" title="object_embed_flag" href="#dfn-object_embed_flag">object embed flag</a> is set and the item has
        the <code>@subject</code> property, and its IRI is in the
        <a class="tref internalDFN" title="map_of_embedded_subjects" href="#dfn-map_of_embedded_subjects">map of embedded subjects</a>, throw a
        <code>Duplicate Embed</code> exception.</li>
      <li>If the <a class="tref internalDFN" title="object_embed_flag" href="#dfn-object_embed_flag">object embed flag</a> is set and the item has
        the <code>@subject</code> property and its IRI is not in the
        <a class="tref internalDFN" title="map_of_embedded_subjects" href="#dfn-map_of_embedded_subjects">map of embedded subjects</a>:
        <ol class="algorithm">
          <li>If the <a class="tref internalDFN" title="explicit_inclusion_flag" href="#dfn-explicit_inclusion_flag">explicit inclusion flag</a> is set,
            then delete any key from the item that does not exist in the
            <a class="tref internalDFN" title="match_frame" href="#dfn-match_frame">match frame</a>, except <code>@subject</code>.</li>
          <li>For each key in the <a class="tref internalDFN" title="match_frame" href="#dfn-match_frame">match frame</a>, except for
            keywords and <code>rdf:type</code>:
          <ol class="algorithm">
            <li>If the key is in the item, then build a new
              <dfn title="recursion_input_list" id="dfn-recursion_input_list">recursion input list</dfn> using the object or objects
              associated with the key. If any object contains an
              <code>@iri</code> value that exists in the
              <a class="tref" title="normalized_input">normalized input</a>, replace the object in the
              <a class="tref" title="recusion_input_list">recusion input list</a> with a new object containing
              the <code>@subject</code> key where the value is the value of
              the <code>@iri</code>, and all of the other key-value pairs for
              that subject. Set the <dfn title="recursion_match_frame" id="dfn-recursion_match_frame">recursion match frame</dfn> to the
              value associated with the <a class="tref internalDFN" title="match_frame" href="#dfn-match_frame">match frame</a>'s key. Replace
              the value associated with the key by recursively calling this
              algorithm using <a class="tref internalDFN" title="recursion_input_list" href="#dfn-recursion_input_list">recursion input list</a>,
              <a class="tref internalDFN" title="recursion_match_frame" href="#dfn-recursion_match_frame">recursion match frame</a> as input.</li>
            <li>If the key is not in the item, add the key to the item and
              set the associated value to an empty array if the
              <a class="tref internalDFN" title="match_frame" href="#dfn-match_frame">match frame</a> key's value is an array
              or <code>null</code> otherwise.</li>
            <li>If value associated with the item's key is <code>null</code>,
              process the <a class="tref internalDFN" title="omit_missing_properties_flag" href="#dfn-omit_missing_properties_flag">omit missing properties flag</a>:
              <ol class="algorithm">
                <li>If the value associated with the key in the
                  <a class="tref internalDFN" title="match_frame" href="#dfn-match_frame">match frame</a> is an array, use the first frame
                  from the array as the <dfn title="property_frame" id="dfn-property_frame">property frame</dfn>, otherwise
                  set the <a class="tref internalDFN" title="property_frame" href="#dfn-property_frame">property frame</a> to an empty object.</li>
                <li>If the <a class="tref internalDFN" title="property_frame" href="#dfn-property_frame">property frame</a> contains an
                <code>@omitDefault</code> keyword, set the
                <a class="tref internalDFN" title="omit_missing_properties_flag" href="#dfn-omit_missing_properties_flag">omit missing properties flag</a> to its value.
                Note: if the keyword exists, but the value is neither
                <code>true</code> or <code>false</code>, set the associated
                flag to <code>true</code>.</li>
                <li>If the <a class="tref internalDFN" title="omit_missing_properties_flag" href="#dfn-omit_missing_properties_flag">omit missing properties flag</a> is set,
                  delete the key in the item. Otherwise, if the
                  <code>@default</code> keyword is set in the
                  <a class="tref internalDFN" title="property_frame" href="#dfn-property_frame">property frame</a> set the item's value to the value
                  of <code>@default</code>.</li>
              </ol></li>
          </ol></li>
        </ol>
      </li><li>If the <a class="tref internalDFN" title="JSON-LD_output" href="#dfn-json-ld_output">JSON-LD output</a> is <code>null</code> set it to
        the item, otherwise, append the item to the
        <a class="tref internalDFN" title="JSON-LD_output" href="#dfn-json-ld_output">JSON-LD output</a>.
    </li></ol>
  </li><li>Return the <a class="tref internalDFN" title="JSON-LD_output" href="#dfn-json-ld_output">JSON-LD output</a>.</li>
</ol>

The final, non-recursive step of the framing algorithm requires the
<a class="tref internalDFN" title="JSON-LD_output" href="#dfn-json-ld_output">JSON-LD output</a> to be compacted according to the
<a href="#compaction-algorithm">Compaction Algorithm</a> by using the
context provided in the <a class="tref internalDFN" title="input_frame" href="#dfn-input_frame">input frame</a>. The resulting value is the
final output of the compaction algorithm and is what should be returned to the
application.

</div>

</div>

<div id="normalization" class="section">
<h3><span class="secno">3.11 </span>Normalization</h3>

<p class="issue">This algorithm is a work in progress, do not implement it.</p>

<p>Normalization is the process of taking <a class="tref internalDFN" title="JSON-LD_input" href="#dfn-json-ld_input">JSON-LD input</a> and
performing a deterministic transformation on that input that results in all
aspects of the graph being fully expanded and named in the
<a class="tref internalDFN" title="JSON-LD_output" href="#dfn-json-ld_output">JSON-LD output</a>. The normalized output is generated in such a way
that any conforming JSON-LD processor will generate identical output
given the same input. The problem is a fairly difficult technical
problem to solve because it requires a directed graph to be ordered into a
set of nodes and edges in a deterministic way. This is easy to do when all of
the nodes have unique names, but very difficult to do when some of the nodes
are not labeled.
</p>

<p>In time, there may be more than one normalization algorithm that will need
to be identified. For identification purposes, this algorithm is named
&quot;Universal Graph Normalization Algorithm 2011&quot;
(<abbr title="Universal Graph Normalization Algorithm 2011">UGNA2011</abbr>).
</p>

<div id="normalization-algorithm-terms" class="section">
<h4><span class="secno">3.11.1 </span>Normalization Algorithm Terms</h4>
 <dl>
   <dt><dfn title="label" id="dfn-label">label</dfn></dt>
   <dd>
     The subject IRI associated with a graph node. The subject IRI is expressed
     using a key-value pair in a <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> where the key is
     <code>@subject</code> and the value is a string that is an IRI or
     a <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> containing the key <code>@iri</code> and
     a value that is a string that is an IRI.
   </dd>
   <dt><dfn title="list_of_expanded_nodes" id="dfn-list_of_expanded_nodes">list of expanded nodes</dfn></dt>
   <dd>
     A list of all nodes in the <a class="tref internalDFN" title="JSON-LD_input" href="#dfn-json-ld_input">JSON-LD input</a> graph containing no
     embedded objects and having all keys and values expanded according to the
     steps in the <a href="#expansion-algorithm">Expansion Algorithm</a>.
   </dd>
   <dt><dfn title="alpha" id="dfn-alpha">alpha</dfn> and <dfn title="beta" id="dfn-beta">beta</dfn> values</dt>
   <dd>
     The words <a class="tref internalDFN" title="alpha" href="#dfn-alpha">alpha</a> and <a class="tref internalDFN" title="beta" href="#dfn-beta">beta</a> refer to the first and
     second nodes or values being examined in an algorithm. The names are
     merely used to refer to each input value to a comparison algorithm.
   </dd>
   <dt><dfn title="renaming_counter" id="dfn-renaming_counter">renaming counter</dfn></dt>
   <dd>
     A counter that is used during the
     <a href="#node-relabeling-algorithm">Node Relabeling Algorithm</a>. The
     counter typically starts at one (1) and counts up for every node that is
     relabeled. There will be two such renaming counters in an implementation
     of the normalization algorithm. The first is the
     <a class="tref internalDFN" title="labeling_counter" href="#dfn-labeling_counter">labeling counter</a> and the second is the
     <a class="tref" title="deterministic_labeling_counter">deterministic labeling counter</a>.
   </dd>
   <dt><dfn title="serialization_label" id="dfn-serialization_label">serialization label</dfn></dt>
   <dd>
     An identifier that is created to aid in the normalization process in the
     <a href="#deep-comparison-algorithm">Deep Comparison Algorithm</a>. The
     value typically takes the form of <code>s&lt;NUMBER&gt;</code> or
     <code>c&lt;NUMBER&gt;</code>.
   </dd>
</dl>
</div>

<div id="normalization-state" class="section">
<h4><span class="secno">3.11.2 </span>Normalization State</h4>

<p>When performing the steps required by the normalization algorithm,
it is helpful to track the many pieces of information in a
data structure called the <dfn title="normalization_state" id="dfn-normalization_state">normalization state</dfn>. Many of these
pieces simply provide indexes into the graph. The information
contained in the <a class="tref internalDFN" title="normalization_state" href="#dfn-normalization_state">normalization state</a> is described below.</p>

<dl>
   <dt><dfn title="node_state" id="dfn-node_state">node state</dfn></dt>
   <dd>
     Each node in the graph will be assigned a <a class="tref internalDFN" title="node_state" href="#dfn-node_state">node state</a>. This
     state contains the information necessary to deterministically
     <a class="tref internalDFN" title="label" href="#dfn-label">label</a> all nodes in the graph. A <a class="tref internalDFN" title="node_state" href="#dfn-node_state">node state</a>
     includes:
     <dl>
        <dt><dfn title="node_reference" id="dfn-node_reference">node reference</dfn></dt>
        <dd>
          A <a class="tref internalDFN" title="node_reference" href="#dfn-node_reference">node reference</a> is a reference to a node in the graph.
          For a given <a class="tref internalDFN" title="node_state" href="#dfn-node_state">node state</a>, its <a class="tref internalDFN" title="node_reference" href="#dfn-node_reference">node reference</a>
          refers to the node that the state is for. When a
          <a class="tref internalDFN" title="node_state" href="#dfn-node_state">node state</a> is created, its <a class="tref internalDFN" title="node_reference" href="#dfn-node_reference">node reference</a>
          should be to the node it is created for.
        </dd>
        <dt><dfn title="outgoing_list" id="dfn-outgoing_list">outgoing list</dfn></dt>
        <dd>
          Lists the <a class="tref internalDFN" title="label" href="#dfn-label">label</a>s for all nodes that are properties of
          the <a class="tref internalDFN" title="node_reference" href="#dfn-node_reference">node reference</a>. This list should be initialized
          by iterating over every object associated with a property in the
          <a class="tref internalDFN" title="node_reference" href="#dfn-node_reference">node reference</a> adding its label if it is another node.
        </dd>
        <dt><dfn title="incoming_list" id="dfn-incoming_list">incoming list</dfn></dt>
        <dd>
          Lists the <a class="tref internalDFN" title="label" href="#dfn-label">label</a>s for all nodes in the graph for which
          the <a class="tref internalDFN" title="node_reference" href="#dfn-node_reference">node reference</a> is a property. This list is
          initialized to an empty list.
        </dd>
        <dt><dfn title="outgoing_serialization_map" id="dfn-outgoing_serialization_map">outgoing serialization map</dfn></dt>
        <dd>
          Maps node <a class="tref internalDFN" title="label" href="#dfn-label">label</a>s to <a class="tref internalDFN" title="serialization_label" href="#dfn-serialization_label-1">serialization label</a>s.
          This map is initialized to an empty map. When this map is populated,
          it will be filled with keys that are the <a class="tref internalDFN" title="label" href="#dfn-label">label</a>s of every node in the
          graph with a label that begins with <code>_:</code> and that has a
          path, via properties, that starts with the
          <a class="tref internalDFN" title="node_reference" href="#dfn-node_reference">node reference</a>.
        </dd>
        <dt><dfn title="outgoing_serialization" id="dfn-outgoing_serialization">outgoing serialization</dfn></dt>
        <dd>
          A string that can be lexicographically compared to the
          <a class="tref internalDFN" title="outgoing_serialization" href="#dfn-outgoing_serialization">outgoing serialization</a>s of other
          <a class="tref internalDFN" title="node_state" href="#dfn-node_state">node state</a>s. It is a representation of the
          <a class="tref internalDFN" title="outgoing_serialization_map" href="#dfn-outgoing_serialization_map">outgoing serialization map</a> and other related
          information. This string is initialized to an empty string.
        </dd>
        <dt><dfn title="incoming_serialization_map" id="dfn-incoming_serialization_map">incoming serialization map</dfn></dt>
        <dd>
          Maps node <a class="tref internalDFN" title="label" href="#dfn-label">label</a>s to <a class="tref internalDFN" title="serialization_label" href="#dfn-serialization_label-1">serialization label</a>s.
          This map is initialized to an empty map. When this map is populated,
          it will be filled with keys that are the <a class="tref internalDFN" title="label" href="#dfn-label">label</a>s of every
          node in the graph with a <a class="tref internalDFN" title="label" href="#dfn-label">label</a> that begins with
          <code>_:</code> and that has a path, via properties, that ends with
          the <a class="tref internalDFN" title="node_reference" href="#dfn-node_reference">node reference</a>.
        </dd>
        <dt><dfn title="incoming_serialization" id="dfn-incoming_serialization">incoming serialization</dfn></dt>
        <dd>
          A string that can be lexicographically compared to the
          <a class="tref internalDFN" title="outgoing_serialization" href="#dfn-outgoing_serialization">outgoing serialization</a>s of other
          <a class="tref internalDFN" title="node_state" href="#dfn-node_state">node state</a>s. It is a representation of the
          <a class="tref internalDFN" title="incoming_serialization_map" href="#dfn-incoming_serialization_map">incoming serialization map</a> and other related
          information. This string is initialized to an empty string.
        </dd>
     </dl>
   </dd>
   <dt><dfn title="node_state_map" id="dfn-node_state_map">node state map</dfn></dt>
   <dd>
     A mapping from a node's <a class="tref internalDFN" title="label" href="#dfn-label">label</a> to a <a class="tref internalDFN" title="node_state" href="#dfn-node_state">node state</a>.
     It is initialized to an empty map.
   </dd>
   <dt><dfn title="labeling_prefix" id="dfn-labeling_prefix">labeling prefix</dfn></dt>
   <dd>
     The labeling prefix is a string that is used as the beginning of a node
     <a class="tref internalDFN" title="label" href="#dfn-label">label</a>. It should be initialized to a random base string that
     starts with the characters <code>_:</code>, is not used by any other
     node's <a class="tref internalDFN" title="label" href="#dfn-label">label</a> in the <a class="tref internalDFN" title="JSON-LD_input" href="#dfn-json-ld_input">JSON-LD input</a>, and does not
     start with the characters <code>_:c14n</code>. The prefix has two uses.
     First it is used to temporarily name nodes during the normalization
     algorithm in a way that doesn't collide with the names that already
     exist as well as the names that will be generated by the normalization
     algorithm. Second, it will eventually be set to <code>_:c14n</code> to
     generate the final, deterministic labels for nodes in the graph. This
     prefix will be concatenated with the <a class="tref internalDFN" title="labeling_counter" href="#dfn-labeling_counter">labeling counter</a> to
     produce a node <a class="tref internalDFN" title="label" href="#dfn-label">label</a>. For example, <code>_:j8r3k</code> is
     a proper initial value for the <a class="tref internalDFN" title="labeling_prefix" href="#dfn-labeling_prefix">labeling prefix</a>.
   </dd>
   <dt><dfn title="labeling_counter" id="dfn-labeling_counter">labeling counter</dfn></dt>
   <dd>
     A counter that is used to label nodes. It is appended to the
     <a class="tref internalDFN" title="labeling_prefix" href="#dfn-labeling_prefix">labeling prefix</a> to create a node <a class="tref internalDFN" title="label" href="#dfn-label">label</a>. It is
     initialized to <code>1</code>.
   </dd>
   <dt><dfn title="map_of_flattened_nodes" id="dfn-map_of_flattened_nodes">map of flattened nodes</dfn></dt>
   <dd>
     A map containing a representation of all nodes in the graph where the
     key is a node <a class="tref internalDFN" title="label" href="#dfn-label">label</a> and the value is a single
     <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> that has no nested sub-objects
     and has had all properties for the same node merged into a single
     <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a>.
   </dd>
</dl>

</div>

<div id="normalization-algorithm" class="section">
<h4><span class="secno">3.11.3 </span>Normalization Algorithm</h4>

<p>The normalization algorithm expands the <a class="tref internalDFN" title="JSON-LD_input" href="#dfn-json-ld_input">JSON-LD input</a>,
flattens the data structure, and creates an initial set of names for all
nodes in the graph. The flattened data structure is then processed by a
node labeling algorithm in order to get a fully expanded and named list of
nodes which is then sorted. The result is a deterministically named and
ordered list of graph nodes.
</p>

<ol class="algorithm">
<li>Expand the <a class="tref internalDFN" title="JSON-LD_input" href="#dfn-json-ld_input">JSON-LD input</a> according to the steps in
the <a href="#expansion-algorithm">Expansion Algorithm</a> and store the
result as the <strong>expanded input</strong>.</li>
<li>Create a <a class="tref internalDFN" title="normalization_state" href="#dfn-normalization_state">normalization state</a>.</li>
<li>Initialize the <a class="tref internalDFN" title="map_of_flattened_nodes" href="#dfn-map_of_flattened_nodes">map of flattened nodes</a> by recursively
processing every <dfn title="expanded_node" id="dfn-expanded_node">expanded node</dfn> in the
<strong>expanded input</strong> in depth-first order:
  <ol class="algorithm">
    <li>If the <a class="tref internalDFN" title="expanded_node" href="#dfn-expanded_node">expanded node</a> is an unlabeled node, add a
      new key-value pair to the <a class="tref internalDFN" title="expanded_node" href="#dfn-expanded_node">expanded node</a>
      where the key is <code>@subject</code> and the value is the
      concatenation of the <a class="tref internalDFN" title="labeling_prefix" href="#dfn-labeling_prefix">labeling prefix</a>
      and the string value of the <a class="tref internalDFN" title="labeling_counter" href="#dfn-labeling_counter">labeling counter</a>.
      Increment the <a class="tref internalDFN" title="labeling_counter" href="#dfn-labeling_counter">labeling counter</a>.</li>
    <li>Add the <a class="tref internalDFN" title="expanded_node" href="#dfn-expanded_node">expanded node</a> to the
      <a class="tref internalDFN" title="map_of_flattened_nodes" href="#dfn-map_of_flattened_nodes">map of flattened nodes</a>:
      <ol class="algorithm">
        <li>If the <a class="tref internalDFN" title="expanded_node" href="#dfn-expanded_node">expanded node</a>'s <a class="tref internalDFN" title="label" href="#dfn-label">label</a> is already
          in the
          <a class="tref internalDFN" title="map_of_flattened_nodes" href="#dfn-map_of_flattened_nodes">map of flattened nodes</a> merge all properties from the
          entry in the <a class="tref internalDFN" title="map_of_flattened_nodes" href="#dfn-map_of_flattened_nodes">map of flattened nodes</a> into the
          <a class="tref internalDFN" title="expanded_node" href="#dfn-expanded_node">expanded node</a>.</li>
        <li>Go through every property associated with an array in the
          <a class="tref internalDFN" title="expanded_node" href="#dfn-expanded_node">expanded node</a> and remove any duplicate IRI entries from
          the array. If the resulting array only has one IRI entry, change it
          from an array to an object.</li>
        <li>Set the entry for the <a class="tref internalDFN" title="expanded_node" href="#dfn-expanded_node">expanded node</a>'s <a class="tref internalDFN" title="label" href="#dfn-label">label</a>
          in the <a class="tref internalDFN" title="map_of_flattened_nodes" href="#dfn-map_of_flattened_nodes">map of flattened nodes</a> to the
          <a class="tref internalDFN" title="expanded_node" href="#dfn-expanded_node">expanded node</a>.
        </li></ol></li>
    <li>After exiting the recursive step, replace the reference to the
      <a class="tref internalDFN" title="expanded_node" href="#dfn-expanded_node">expanded node</a> with an object containing a single
       key-value pair where the key is <code>@iri</code> and the value is
       the value of the <code>@subject</code> key in the node.</li>
  </ol></li>
<li>For every entry in the <a class="tref internalDFN" title="map_of_flattened_nodes" href="#dfn-map_of_flattened_nodes">map of flattened nodes</a>, insert a
  key-value pair into the <a class="tref internalDFN" title="node_state_map" href="#dfn-node_state_map">node state map</a> where the key is the
  key from the <a class="tref internalDFN" title="map_of_flattened_nodes" href="#dfn-map_of_flattened_nodes">map of flattened nodes</a> and the value is a
  <a class="tref internalDFN" title="node_state" href="#dfn-node_state">node state</a> where its <a class="tref internalDFN" title="node_reference" href="#dfn-node_reference">node reference</a> refers to
  the value from the <a class="tref internalDFN" title="map_of_flattened_nodes" href="#dfn-map_of_flattened_nodes">map of flattened nodes</a>.
</li><li>Populate the <a class="tref internalDFN" title="incoming_list" href="#dfn-incoming_list">incoming list</a> for each <a class="tref internalDFN" title="node_state" href="#dfn-node_state">node state</a>
  by iterating over every node in the graph and adding its <a class="tref internalDFN" title="label" href="#dfn-label">label</a>
  to the <a class="tref internalDFN" title="incoming_list" href="#dfn-incoming_list">incoming list</a> associated with each node found in its
  properties.</li>
<li>For every entry in the <a class="tref internalDFN" title="node_state_map" href="#dfn-node_state_map">node state map</a> that has a
<a class="tref internalDFN" title="label" href="#dfn-label">label</a> that begins with <code>_:c14n</code>, relabel the node
using the <a href="#node-relabeling-algorithm">Node Relabeling Algorithm</a>.
</li><li>Label all of the nodes that contain a <code>@subject</code> key associated
with a value starting with <code>_:</code> according to the steps in the
<a href="#deterministic-labeling-algorithm">Deterministic Labeling Algorithm</a>.
</li>
</ol>
</div>

<div id="node-relabeling-algorithm" class="section">
<h4><span class="secno">3.11.4 </span>Node Relabeling Algorithm</h4>

<p>This algorithm renames a node by generating a unique
<dfn title="new_label" id="dfn-new_label">new label</dfn> and updating all references to that <a class="tref internalDFN" title="label" href="#dfn-label">label</a>
in the <a class="tref internalDFN" title="node_state_map" href="#dfn-node_state_map">node state map</a>. The <dfn title="old_label" id="dfn-old_label">old label</dfn> and the
<a class="tref internalDFN" title="normalization_state" href="#dfn-normalization_state">normalization state</a> must be given as an input to the
algorithm. The <a class="tref internalDFN" title="old_label" href="#dfn-old_label">old label</a> is the current <a class="tref internalDFN" title="label" href="#dfn-label">label</a> of
the node that is to be relabeled.

</p><p>The node relabeling algorithm is as follows:</p>

<ol class="algorithm">
  <li>If the <a class="tref internalDFN" title="labeling_prefix" href="#dfn-labeling_prefix">labeling prefix</a> is <code>_:c14n</code> and the
    <a class="tref internalDFN" title="old_label" href="#dfn-old_label">old label</a> begins with <code>_:c14n</code> then return as
    the node has already been renamed.
  </li>
  <li>Generate the <dfn title="new_label" id="dfn-new_label-1">new label</dfn> by concatenating the
    <a class="tref internalDFN" title="labeling_prefix" href="#dfn-labeling_prefix">labeling prefix</a> with the string value of the
    <a class="tref internalDFN" title="labeling_counter" href="#dfn-labeling_counter">labeling counter</a>. Increment the <a class="tref internalDFN" title="labeling_counter" href="#dfn-labeling_counter">labeling counter</a>.
  </li>
  <li>For the <a class="tref internalDFN" title="node_state" href="#dfn-node_state">node state</a> associated with the
  <a class="tref internalDFN" title="old_label" href="#dfn-old_label">old label</a>, update every node in the <a class="tref internalDFN" title="incoming_list" href="#dfn-incoming_list">incoming list</a>
  by changing all the properties that reference the <a class="tref internalDFN" title="old_label" href="#dfn-old_label">old label</a> to
  the <a class="tref internalDFN" title="new_label" href="#dfn-new_label-1">new label</a>.
  </li>
  <li>Change the <a class="tref internalDFN" title="old_label" href="#dfn-old_label">old label</a> key in the <a class="tref internalDFN" title="node_state_map" href="#dfn-node_state_map">node state map</a>
    to the <a class="tref internalDFN" title="new_label" href="#dfn-new_label-1">new label</a> and set the associated
    <a class="tref internalDFN" title="node_reference" href="#dfn-node_reference">node reference</a>'s <a class="tref internalDFN" title="label" href="#dfn-label">label</a> to the
    <a class="tref internalDFN" title="new_label" href="#dfn-new_label-1">new label</a>.
  </li>
</ol>
</div>

<div id="deterministic-labeling-algorithm" class="section">
<h4><span class="secno">3.11.5 </span>Deterministic Labeling Algorithm</h4>

<p>The deterministic labeling algorithm takes the
<a class="tref internalDFN" title="normalization_state" href="#dfn-normalization_state">normalization state</a>
and produces a <dfn title="list_of_finished_nodes" id="dfn-list_of_finished_nodes">list of finished nodes</dfn> that is sorted and
contains deterministically named and expanded nodes from the graph.

</p><ol class="algorithm">
  <li>Set the <a class="tref internalDFN" title="labeling_prefix" href="#dfn-labeling_prefix">labeling prefix</a> to <code>_:c14n</code>, the
    <a class="tref internalDFN" title="labeling_counter" href="#dfn-labeling_counter">labeling counter</a> to <code>1</code>,
    the <dfn title="list_of_finished_nodes" id="dfn-list_of_finished_nodes-1">list of finished nodes</dfn> to an empty array, and create
    an empty array, the <dfn title="list_of_unfinished_nodes" id="dfn-list_of_unfinished_nodes">list of unfinished nodes</dfn>.</li>
  <li>For each <a class="tref internalDFN" title="node_reference" href="#dfn-node_reference">node reference</a> in the <a class="tref internalDFN" title="node_state_map" href="#dfn-node_state_map">node state map</a>:
    <ol class="algorithm">
      <li>If the node's <a class="tref internalDFN" title="label" href="#dfn-label">label</a> does not start with <code>_:</code>
        then put the <a class="tref internalDFN" title="node_reference" href="#dfn-node_reference">node reference</a> in the
        <a class="tref internalDFN" title="list_of_finished_nodes" href="#dfn-list_of_finished_nodes-1">list of finished nodes</a>.
      </li>
      <li>If the node's <a class="tref internalDFN" title="label" href="#dfn-label">label</a> does start with <code>_:</code>
        then put the <a class="tref internalDFN" title="node_reference" href="#dfn-node_reference">node reference</a> in the
        <a class="tref internalDFN" title="list_of_unfinished_nodes" href="#dfn-list_of_unfinished_nodes">list of unfinished nodes</a>.
      </li>
    </ol>
  </li>
  <li>Append to the <a class="tref internalDFN" title="list_of_finished_nodes" href="#dfn-list_of_finished_nodes-1">list of finished nodes</a> by processing
    the remainder of the <a class="tref internalDFN" title="list_of_unfinished_nodes" href="#dfn-list_of_unfinished_nodes">list of unfinished nodes</a> until it is
    empty:
    <ol class="algorithm">
      <li>Sort the <a class="tref internalDFN" title="list_of_unfinished_nodes" href="#dfn-list_of_unfinished_nodes">list of unfinished nodes</a> in descending order
        according to the
        <a href="#deep-comparison-algorithm">Deep Comparison Algorithm</a> to
        determine the sort order.</li>
      <li>Create a <dfn title="list_of_labels" id="dfn-list_of_labels">list of labels</dfn> and initialize it to an
        empty array.</li>
      <li>For the first node from the <a class="tref internalDFN" title="list_of_unfinished_nodes" href="#dfn-list_of_unfinished_nodes">list of unfinished nodes</a>:
        <ol class="algorithm">
          <li>Add its <a class="tref internalDFN" title="label" href="#dfn-label">label</a> to the <a class="tref internalDFN" title="list_of_labels" href="#dfn-list_of_labels">list of labels</a>.
          </li>
          <li>For each key-value pair from its associated
            <a class="tref internalDFN" title="outgoing_serialization_map" href="#dfn-outgoing_serialization_map">outgoing serialization map</a>, add the key to a list and
            then sort the list according to the lexicographical order of the
            keys' associated values. Append the list to the
            <a class="tref" title="list_of_nodes_to_label">list of nodes to label</a>.
          </li>
          <li>For each key-value pair from its associated
            <a class="tref internalDFN" title="incoming_serialization_map" href="#dfn-incoming_serialization_map">incoming serialization map</a>, add the key to a list and
            then sort the list according to the lexicographical order of the
            keys' associated values. Append the list to the
            <a class="tref" title="list_of_nodes_to_label">list of nodes to label</a>.
          </li></ol></li>
      <li>For each <a class="tref internalDFN" title="label" href="#dfn-label">label</a> in the <a class="tref internalDFN" title="list_of_labels" href="#dfn-list_of_labels">list of labels</a>,
        relabel the associated node according to the
        <a href="#node-relabeling-algorithm">Node Relabeling Algorithm</a>. If
        any <a class="tref internalDFN" title="outgoing_serialization_map" href="#dfn-outgoing_serialization_map">outgoing serialization map</a> contains a key that
        matches the <a class="tref internalDFN" title="label" href="#dfn-label">label</a>, clear the map and set the associated
        <a class="tref internalDFN" title="outgoing_serialization" href="#dfn-outgoing_serialization">outgoing serialization</a> to an empty string. If any
        <a class="tref internalDFN" title="incoming_serialization_map" href="#dfn-incoming_serialization_map">incoming serialization map</a> contains a key that
        matches the <a class="tref internalDFN" title="label" href="#dfn-label">label</a>, clear the map and set the associated
        <a class="tref internalDFN" title="incoming_serialization" href="#dfn-incoming_serialization">incoming serialization</a> to an empty string.
      </li>
      <li>
        Remove each node with a <a class="tref internalDFN" title="label" href="#dfn-label">label</a> that starts with
        <code>_:c14n</code> from the <a class="tref internalDFN" title="list_of_unfinished_nodes" href="#dfn-list_of_unfinished_nodes">list of unfinished nodes</a> and
        add it to the <a class="tref internalDFN" title="list_of_finished_nodes" href="#dfn-list_of_finished_nodes-1">list of finished nodes</a>.
      </li>
    </ol>
  </li>
  <li>Sort the <a class="tref internalDFN" title="list_of_finished_nodes" href="#dfn-list_of_finished_nodes-1">list of finished nodes</a> in descending order
    according to the
    <a href="#deep-comparison-algorithm">Deep Comparison Algorithm</a> to
    determine the sort order.</li>
</ol>
</div>

<div id="shallow-comparison-algorithm" class="section">
<h4><span class="secno">3.11.6 </span>Shallow Comparison Algorithm</h4>

<p>
The shallow comparison algorithm takes two unlabeled nodes,
<a class="tref internalDFN" title="alpha" href="#dfn-alpha">alpha</a> and <a class="tref internalDFN" title="beta" href="#dfn-beta">beta</a>, as input and
determines which one should come first in a sorted list. The following
algorithm determines the steps that are executed in order to determine the
node that should come first in a list:
</p>

<ol class="algorithm">
  <li>Compare the total number of node properties. The node with fewer
    properties is first.</li>
  <li>Lexicographically sort the property IRIs for each node and compare
    the sorted lists. If an IRI is found to be lexicographically smaller, the
    node containing that IRI is first.</li>
  <li>Compare the values of each property against one another:
    <ol class="algorithm">
      <li>The node associated with fewer property values is first.
      </li>
      <li>Create an <dfn title="alpha_list" id="dfn-alpha_list">alpha list</dfn> by adding all values associated
        with the <a class="tref internalDFN" title="alpha" href="#dfn-alpha">alpha</a> property that are not unlabeled nodes.
      </li>
      <li>Create a <dfn title="beta_list" id="dfn-beta_list">beta list</dfn> by adding all values associated
        with the <a class="tref internalDFN" title="beta" href="#dfn-beta">beta</a> property that is not an unlabeled node.
      </li>
      <li>Compare the length of <a class="tref internalDFN" title="alpha_list" href="#dfn-alpha_list">alpha list</a> and
        <a class="tref internalDFN" title="beta_list" href="#dfn-beta_list">beta list</a>. The node associated with the list containing
        the fewer number of items is first.</li>
      <li>Sort <a class="tref internalDFN" title="alpha_list" href="#dfn-alpha_list">alpha list</a> and <a class="tref internalDFN" title="beta_list" href="#dfn-beta_list">beta list</a> according to
        the
        <a href="#object-comparison-algorithm">Object Comparison Algorithm</a>.
        For each offset into the <a class="tref internalDFN" title="alpha_list" href="#dfn-alpha_list">alpha list</a>, compare the item
        at the offset against the item at the same offset in the
        <a class="tref internalDFN" title="beta_list" href="#dfn-beta_list">beta list</a> according to the
        <a href="#object-comparison-algorithm">Object Comparison Algorithm</a>.
        The node associated with the lesser item is first.
    </li></ol></li>
  <li>Process the <a class="tref internalDFN" title="incoming_list" href="#dfn-incoming_list">incoming list</a>s associated with each node to
    determine order:
    <ol class="algorithm">
      <li>The node with the shortest <a class="tref internalDFN" title="incoming_list" href="#dfn-incoming_list">incoming list</a> is first.</li>
      <li>Sort the <a class="tref internalDFN" title="incoming_list" href="#dfn-incoming_list">incoming list</a>s according to incoming property
         and then incoming <a class="tref internalDFN" title="label" href="#dfn-label">label</a>.
      </li><li>The node associated with the fewest number of incoming nodes is
        first.</li>
      <li>For each offset into the <a class="tref internalDFN" title="incoming_list" href="#dfn-incoming_list">incoming list</a>s,
        compare the associated properties and <a class="tref internalDFN" title="label" href="#dfn-label">label</a>s:
        <ol class="algorithm">
          <li>The node associated with a <a class="tref internalDFN" title="label" href="#dfn-label">label</a> that does not begin with
            <code>_:</code> is first.
          </li>
          <li>If the nodes' <a class="tref internalDFN" title="label" href="#dfn-label">label</a>s do not begin with
            <code>_:</code>, then the node associated with the
            lexicographically lesser <a class="tref internalDFN" title="label" href="#dfn-label">label</a> is first.</li>
          
          <li>The node associated with the lexicographically lesser associated
            property is first.
          </li>
          <li>The node with the <a class="tref internalDFN" title="label" href="#dfn-label">label</a> that does not begin with
            <code>_:c14n</code> is first.
          </li>
          <li>The node with the lexicographically lesser <a class="tref internalDFN" title="label" href="#dfn-label">label</a>
            is first.
          </li>
        </ol>
    </li></ol></li>
  <li>Otherwise, the nodes are equivalent.</li>
</ol></div>

<div id="object-comparison-algorithm" class="section">
<h4><span class="secno">3.11.7 </span>Object Comparison Algorithm</h4>

<p>
The object comparison algorithm is designed to compare two graph node
property values, <a class="tref internalDFN" title="alpha" href="#dfn-alpha">alpha</a> and <a class="tref internalDFN" title="beta" href="#dfn-beta">beta</a>, against the other.
The algorithm is useful when sorting two lists of graph node properties.
</p>

<ol class="algorithm">
  <li>If one of the values is a <a class="tref internalDFN" title="string" href="#dfn-string">string</a> and the other is not, the value that is
    a string is first.
  </li>
  <li>If both values are <a class="tref internalDFN" title="string" href="#dfn-string">string</a>s, the lexicographically lesser string is
    first.
  </li>
  <li>If one of the values is a literal and the other is not, the value that is
    a literal is first.
  </li>
  <li>If both values are literals:
    <ol class="algorithm">
      <li>The lexicographically lesser string associated with
        <code>@literal</code> is first.
      </li>
      <li>The lexicographically lesser string associated with
        <code>@datatype</code> is first.
      </li>
      <li>The lexicographically lesser string associated with
        <code>@language</code> is first.
      </li>
    </ol>
  </li>
  <li>If both values are expanded IRIs, the
    lexicographically lesser string associated with <code>@iri</code>
    is first.</li>
  <li>Otherwise, the two values are equivalent.</li>
</ol>

</div>

<div id="deep-comparison-algorithm" class="section">
<h4><span class="secno">3.11.8 </span>Deep Comparison Algorithm</h4>

<p>
The deep comparison algorithm is used to compare the difference between two
nodes, <a class="tref internalDFN" title="alpha" href="#dfn-alpha">alpha</a> and <a class="tref internalDFN" title="beta" href="#dfn-beta">beta</a>.
A deep comparison takes the incoming and outgoing node edges in
a graph into account if the number of properties and value of those properties
are identical. The algorithm is helpful when sorting a list of nodes and will
return whichever node should be placed first in a list if the two nodes are
not truly equivalent.
</p>

<p>When performing the steps required by the deep comparison algorithm, it
is helpful to track state information about mappings. The information
contained in a <a class="tref internalDFN" title="mapping_state" href="#dfn-mapping_state">mapping state</a> is described below.</p>

<dl class="algorithm">
   <dt><dfn title="mapping_state" id="dfn-mapping_state">mapping state</dfn></dt>
   <dd>
     <dl>
        <dt><dfn title="mapping_counter" id="dfn-mapping_counter">mapping counter</dfn></dt>
        <dd>
          Keeps track of the number of nodes that have been mapped to
          <a class="tref" title="serialization_labels">serialization labels</a>. It is initialized to
          <code>1</code>.
        </dd>
        <dt><dfn title="processed_labels_map" id="dfn-processed_labels_map">processed labels map</dfn></dt>
        <dd>
          Keeps track of the <a class="tref internalDFN" title="label" href="#dfn-label">label</a>s of nodes that have already
          been assigned <a class="tref internalDFN" title="serialization_label" href="#dfn-serialization_label-1">serialization label</a>s. It is initialized
          to an empty map.
        </dd>
        <dt><dfn title="serialized_labels_map" id="dfn-serialized_labels_map">serialized labels map</dfn></dt>
        <dd>
          Maps a node <a class="tref internalDFN" title="label" href="#dfn-label">label</a> to its associated
          <a class="tref internalDFN" title="serialization_label" href="#dfn-serialization_label-1">serialization label</a>. It is initialized to an empty map.
        </dd>
        <dt><dfn title="adjacent_info_map" id="dfn-adjacent_info_map">adjacent info map</dfn></dt>
        <dd>
          Maps a <a class="tref internalDFN" title="serialization_label" href="#dfn-serialization_label-1">serialization label</a> to the node
          <a class="tref internalDFN" title="label" href="#dfn-label">label</a> associated with it, the list of sorted
          <a class="tref internalDFN" title="serialization_label" href="#dfn-serialization_label-1">serialization label</a>s for adjacent nodes, and the map of
          adjacent node <a class="tref" title="serialiation_label">serialiation label</a>s to their associated
          node <a class="tref internalDFN" title="label" href="#dfn-label">label</a>s. It is initialized to an empty map.
        </dd>
        <dt><dfn title="key_stack" id="dfn-key_stack">key stack</dfn></dt>
        <dd>
          A stack where each element contains an array of adjacent
          <a class="tref internalDFN" title="serialization_label" href="#dfn-serialization_label-1">serialization label</a>s and an index into that array. It
          is initialized to a stack containing a single element where its
          array contains a single string element <code>s1</code> and its
          index is set to <code>0</code>.
        </dd>
        <dt><dfn title="serialized_keys" id="dfn-serialized_keys">serialized keys</dfn></dt>
        <dd>
          Keeps track of which <a class="tref internalDFN" title="serialization_label" href="#dfn-serialization_label-1">serialization label</a>s have already
          been written at least once to the <a class="tref internalDFN" title="serialization_string" href="#dfn-serialization_string">serialization string</a>.
          It is initialized to an empty map.
        </dd>
        <dt><dfn title="serialization_string" id="dfn-serialization_string">serialization string</dfn></dt>
        <dd>
          A string that is incrementally updated as a serialization is built.
          It is initialized to an empty string.
        </dd>
     </dl>
   </dd>
</dl>

<p>The deep comparison algorithm is as follows:</p>

<ol class="algorithm">
  <li>Perform a comparison between <a class="tref internalDFN" title="alpha" href="#dfn-alpha">alpha</a> and <a class="tref internalDFN" title="beta" href="#dfn-beta">beta</a>
    according to the
    <a href="#shallow-comparison-algorithm">Shallow Comparison Algorithm</a>.
    If the result does not show that the two nodes are equivalent, return
    the result.
    </li>
  <li>Compare incoming and outgoing edges for each node, updating their
    associated <a class="tref internalDFN" title="node_state" href="#dfn-node_state">node state</a> as each node is processed:
    <ol class="algorithm">
      <li>If the <a class="tref internalDFN" title="outgoing_serialization_map" href="#dfn-outgoing_serialization_map">outgoing serialization map</a> for <a class="tref internalDFN" title="alpha" href="#dfn-alpha">alpha</a>
        is empty, generate the serialization according to the
        <a href="#node-serialization-algorithm">Node Serialization Algorithm</a>.
        Provide <a class="tref internalDFN" title="alpha" href="#dfn-alpha">alpha</a>'s <a class="tref internalDFN" title="node_state" href="#dfn-node_state">node state</a>, a new
        <a class="tref internalDFN" title="mapping_state" href="#dfn-mapping_state">mapping state</a>,
        <code>outgoing direction</code> to the algorithm as inputs.
      </li><li>If the <a class="tref internalDFN" title="outgoing_serialization_map" href="#dfn-outgoing_serialization_map">outgoing serialization map</a> for <a class="tref internalDFN" title="beta" href="#dfn-beta">beta</a>
        is empty, generate the serialization according to the
        <a href="#node-serialization-algorithm">Node Serialization Algorithm</a>.
        Provide <a class="tref internalDFN" title="beta" href="#dfn-beta">beta</a>'s <a class="tref internalDFN" title="node_state" href="#dfn-node_state">node state</a>, a new
        <a class="tref internalDFN" title="mapping_state" href="#dfn-mapping_state">mapping state</a>, and
        <code>outgoing direction</code> to the algorithm as inputs.
      </li><li>If <a class="tref internalDFN" title="alpha" href="#dfn-alpha">alpha</a>'s <a class="tref internalDFN" title="outgoing_serialization" href="#dfn-outgoing_serialization">outgoing serialization</a> is
        lexicographically less than <a class="tref internalDFN" title="beta" href="#dfn-beta">beta</a>'s, then
        <a class="tref internalDFN" title="alpha" href="#dfn-alpha">alpha</a> is first. If it is greater, then <a class="tref internalDFN" title="beta" href="#dfn-beta">beta</a>
        is first.</li>
      <li>If the <a class="tref internalDFN" title="incoming_serialization_map" href="#dfn-incoming_serialization_map">incoming serialization map</a> for <a class="tref internalDFN" title="alpha" href="#dfn-alpha">alpha</a>
        is empty, generate the serialization according to the
        <a href="#node-serialization-algorithm">Node Serialization Algorithm</a>.
        Provide <a class="tref internalDFN" title="alpha" href="#dfn-alpha">alpha</a>'s <a class="tref internalDFN" title="node_state" href="#dfn-node_state">node state</a>, a new
        <a class="tref internalDFN" title="mapping_state" href="#dfn-mapping_state">mapping state</a> with its <a class="tref internalDFN" title="serialized_labels_map" href="#dfn-serialized_labels_map">serialized labels map</a>
        set to a copy of <a class="tref internalDFN" title="alpha" href="#dfn-alpha">alpha</a>'s
        <a class="tref internalDFN" title="outgoing_serialization_map" href="#dfn-outgoing_serialization_map">outgoing serialization map</a>, and
        <code>incoming direction</code> to the algorithm as inputs.
      </li><li>If the <a class="tref internalDFN" title="incoming_serialization_map" href="#dfn-incoming_serialization_map">incoming serialization map</a> for <a class="tref internalDFN" title="beta" href="#dfn-beta">beta</a>
        is empty, generate the serialization according to the
        <a href="#node-serialization-algorithm">Node Serialization Algorithm</a>.
        Provide <a class="tref internalDFN" title="beta" href="#dfn-beta">beta</a>'s <a class="tref internalDFN" title="node_state" href="#dfn-node_state">node state</a>, a new
        <a class="tref internalDFN" title="mapping_state" href="#dfn-mapping_state">mapping state</a> with its <a class="tref internalDFN" title="serialized_labels_map" href="#dfn-serialized_labels_map">serialized labels map</a>
        set to a copy of <a class="tref internalDFN" title="beta" href="#dfn-beta">beta</a>'s
        <a class="tref internalDFN" title="outgoing_serialization_map" href="#dfn-outgoing_serialization_map">outgoing serialization map</a>, and
        <code>incoming direction</code> to the algorithm as inputs.
      </li><li>If <a class="tref internalDFN" title="alpha" href="#dfn-alpha">alpha</a>'s <a class="tref internalDFN" title="incoming_serialization" href="#dfn-incoming_serialization">incoming serialization</a> is
        lexicographically less than <a class="tref internalDFN" title="beta" href="#dfn-beta">beta</a>'s, then
        <a class="tref internalDFN" title="alpha" href="#dfn-alpha">alpha</a> is first. If it is greater, then <a class="tref internalDFN" title="beta" href="#dfn-beta">beta</a>
        is first.</li>
    </ol></li>
</ol>
</div>

<div id="node-serialization-algorithm" class="section">
<h4><span class="secno">3.11.9 </span>Node Serialization Algorithm</h4>

<p>
The node serialization algorithm takes a <a class="tref internalDFN" title="node_state" href="#dfn-node_state">node state</a>, a
<a class="tref internalDFN" title="mapping_state" href="#dfn-mapping_state">mapping state</a>, and a <dfn title="direction" id="dfn-direction">direction</dfn> (either
<code>outgoing direction</code> or <code>incoming direction</code>) as
inputs and generates a deterministic serialization for the
<a class="tref internalDFN" title="node_reference" href="#dfn-node_reference">node reference</a>.
</p>

<ol class="algorithm">
<li>If the <a class="tref internalDFN" title="label" href="#dfn-label">label</a> exists in the
  <a class="tref internalDFN" title="processed_labels_map" href="#dfn-processed_labels_map">processed labels map</a>, terminate the algorithm as the
  <a class="tref internalDFN" title="serialization_label" href="#dfn-serialization_label-1">serialization label</a> has already been created.
</li>
<li>Set the value associated with the <a class="tref internalDFN" title="label" href="#dfn-label">label</a> in the
  <a class="tref internalDFN" title="processed_labels_map" href="#dfn-processed_labels_map">processed labels map</a> to <code>true</code>.
</li>
<li>Generate the next <dfn title="serialization_label" id="dfn-serialization_label-1">serialization label</dfn> for the
  <a class="tref internalDFN" title="label" href="#dfn-label">label</a> according to the
  <a href="#serialization-label-generation-algorithm">Serialization Label Generation Algorithm</a>.
</li>
<li>Create an empty map called the <dfn title="adjacent_serialized_labels_map" id="dfn-adjacent_serialized_labels_map">adjacent serialized labels map</dfn>
that will store mappings from <a class="tref" title="serialized_label">serialized label</a>s to adjacent
node <a class="tref internalDFN" title="label" href="#dfn-label">label</a>s.</li>
<li>Create an empty array called the
<dfn title="adjacent_unserialized_labels_list" id="dfn-adjacent_unserialized_labels_list">adjacent unserialized labels list</dfn> that will store
<a class="tref internalDFN" title="label" href="#dfn-label">label</a>s of adjacent nodes that haven't been assigned
<a class="tref internalDFN" title="serialization_label" href="#dfn-serialization_label-1">serialization label</a>s yet.
</li>
<li>For every <a class="tref internalDFN" title="label" href="#dfn-label">label</a> in a list, where the list the <a class="tref internalDFN" title="outgoing_list" href="#dfn-outgoing_list">outgoing list</a> if
the <a class="tref internalDFN" title="direction" href="#dfn-direction">direction</a> is <code>outgoing direction</code> and the
<a class="tref internalDFN" title="incoming_list" href="#dfn-incoming_list">incoming list</a> otherwise, if the <a class="tref internalDFN" title="label" href="#dfn-label">label</a> starts with
<code>_:</code>, it is the <dfn title="target_node_label" id="dfn-target_node_label">target node label</dfn>:
  <ol class="algorithm">
    <li>Look up the <a class="tref internalDFN" title="target_node_label" href="#dfn-target_node_label">target node label</a> in the
      <a class="tref internalDFN" title="processed_labels_map" href="#dfn-processed_labels_map">processed labels map</a> and if a mapping exists,
      update the <a class="tref internalDFN" title="adjacent_serialized_labels_map" href="#dfn-adjacent_serialized_labels_map">adjacent serialized labels map</a> where the key is
      the value in the <a class="tref" title="serialization_map">serialization map</a> and the value is the
      <a class="tref internalDFN" title="target_node_label" href="#dfn-target_node_label">target node label</a>.</li>
    <li>Otherwise, add the <a class="tref internalDFN" title="target_node_label" href="#dfn-target_node_label">target node label</a> to the
      <a class="tref internalDFN" title="adjacent_unserialized_labels_list" href="#dfn-adjacent_unserialized_labels_list">adjacent unserialized labels list</a>.
  </li></ol>
</li>
<li>Set the <dfn title="maximum_serialization_combinations" id="dfn-maximum_serialization_combinations">maximum serialization combinations</dfn> to
  <code>1</code> or the length of the
  <a class="tref internalDFN" title="adjacent_unserialized_labels_list" href="#dfn-adjacent_unserialized_labels_list">adjacent unserialized labels list</a>, whichever is greater.</li>
<li>While the <a class="tref internalDFN" title="maximum_serialization_combinations" href="#dfn-maximum_serialization_combinations">maximum serialization combinations</a> is greater than
  <code>0</code>, perform the
  <a href="#combinatorial-serialization-algorithm">Combinatorial Serialization Algorithm</a>
  passing the <a class="tref internalDFN" title="node_state" href="#dfn-node_state">node state</a>, the <a class="tref internalDFN" title="mapping_state" href="#dfn-mapping_state">mapping state</a> for the
  first iteration and a copy of it for each subsequent iteration, the
  generated <a class="tref internalDFN" title="serialization_label" href="#dfn-serialization_label-1">serialization label</a>, the <a class="tref internalDFN" title="direction" href="#dfn-direction">direction</a>,
  the <a class="tref internalDFN" title="adjacent_serialized_labels_map" href="#dfn-adjacent_serialized_labels_map">adjacent serialized labels map</a>, and the
  <a class="tref internalDFN" title="adjacent_unserialized_labels_list" href="#dfn-adjacent_unserialized_labels_list">adjacent unserialized labels list</a>.
  Decrement the <a class="tref internalDFN" title="maximum_serialization_combinations" href="#dfn-maximum_serialization_combinations">maximum serialization combinations</a> by
  <code>1</code> for each iteration.
</li></ol>

</div>

<div id="serialization-label-generation-algorithm" class="section">
<h4><span class="secno">3.11.10 </span>Serialization Label Generation Algorithm</h4>

<p>
The algorithm generates a <a class="tref internalDFN" title="serialization_label" href="#dfn-serialization_label-1">serialization label</a> given a
<a class="tref internalDFN" title="label" href="#dfn-label">label</a> and a <a class="tref internalDFN" title="mapping_state" href="#dfn-mapping_state">mapping state</a> and returns the
<a class="tref internalDFN" title="serialization_label" href="#dfn-serialization_label-1">serialization label</a>.
</p>

 <ol class="algorithm">
   <li>If the <a class="tref internalDFN" title="label" href="#dfn-label">label</a> is already in the
     <a class="tref" title="serialization_labels_map">serialization labels map</a>, return its associated value.
   </li>
   <li>If the <a class="tref internalDFN" title="label" href="#dfn-label">label</a> starts with the string <code>_:c14n</code>,
     the <a class="tref internalDFN" title="serialization_label" href="#dfn-serialization_label-1">serialization label</a> is the letter <code>c</code>
     followed by the number that follows <code>_:c14n</code> in the
     <a class="tref internalDFN" title="label" href="#dfn-label">label</a>.
   </li>
   <li>Otherwise, the <a class="tref internalDFN" title="serialization_label" href="#dfn-serialization_label-1">serialization label</a> is the
     letter <code>s</code> followed by the string value of
     <a class="tref" title="mapping_count">mapping count</a>. Increment the <a class="tref" title="mapping_count">mapping count</a> by
     <code>1</code>.
   </li>
   <li>Create a new key-value pair in the <a class="tref" title="serialization_labels_map">serialization labels map</a>
     where the key is the <a class="tref internalDFN" title="label" href="#dfn-label">label</a> and the value is the
     generated <a class="tref internalDFN" title="serialization_label" href="#dfn-serialization_label-1">serialization label</a>.
   </li>
 </ol>
</div>

<div id="combinatorial-serialization-algorithm" class="section">
<h4><span class="secno">3.11.11 </span>Combinatorial Serialization Algorithm</h4>

<p>
The combinatorial serialization algorithm takes a <a class="tref internalDFN" title="node_state" href="#dfn-node_state">node state</a>, a
<a class="tref internalDFN" title="mapping_state" href="#dfn-mapping_state">mapping state</a>, a <a class="tref internalDFN" title="serialization_label" href="#dfn-serialization_label-1">serialization label</a>, a
<a class="tref internalDFN" title="direction" href="#dfn-direction">direction</a>, a <a class="tref internalDFN" title="adjacent_serialized_labels_map" href="#dfn-adjacent_serialized_labels_map">adjacent serialized labels map</a>,
and a <a class="tref internalDFN" title="adjacent_unserialized_labels_list" href="#dfn-adjacent_unserialized_labels_list">adjacent unserialized labels list</a> as inputs and generates
the lexicographically least serialization of nodes relating to the
<a class="tref internalDFN" title="node_reference" href="#dfn-node_reference">node reference</a>.
</p>

<ol class="algorithm">
  <li>If the <a class="tref internalDFN" title="adjacent_unserialized_labels_list" href="#dfn-adjacent_unserialized_labels_list">adjacent unserialized labels list</a> is not empty:
    <ol class="algorithm">
      <li>Copy the <a class="tref internalDFN" title="adjacent_serialized_labels_map" href="#dfn-adjacent_serialized_labels_map">adjacent serialized labels map</a> to the
        <dfn title="adjacent_serialized_labels_map_copy" id="dfn-adjacent_serialized_labels_map_copy">adjacent serialized labels map copy</dfn>.</li>
      <li>Remove the first <a class="tref" title="unserialized_label">unserialized label</a> from the
        <a class="tref internalDFN" title="adjacent_unserialized_labels_list" href="#dfn-adjacent_unserialized_labels_list">adjacent unserialized labels list</a> and create a new
        <dfn title="new_serialization_label" id="dfn-new_serialization_label">new serialization label</dfn> according to the
        <a href="#serialization-label-generation-algorithm">Serialization Label Generation Algorithm</a>.
      </li><li>Create a new key-value mapping in the
        <a class="tref internalDFN" title="adjacent_serialized_labels_map_copy" href="#dfn-adjacent_serialized_labels_map_copy">adjacent serialized labels map copy</a>
        where the key is the <a class="tref internalDFN" title="new_serialization_label" href="#dfn-new_serialization_label">new serialization label</a> and the value
        is the <a class="tref" title="unserialized_label">unserialized label</a>.
      </li><li>Set the <dfn title="maximum_serialization_rotations" id="dfn-maximum_serialization_rotations">maximum serialization rotations</dfn> to
        <code>1</code> or the length of the
        <a class="tref internalDFN" title="adjacent_unserialized_labels_list" href="#dfn-adjacent_unserialized_labels_list">adjacent unserialized labels list</a>, whichever is greater.
      </li>
      <li>While the <a class="tref internalDFN" title="maximum_serialization_rotations" href="#dfn-maximum_serialization_rotations">maximum serialization rotations</a> is greater than
        <code>0</code>:
        <ol class="algorithm">
          <li>Recursively perform the
            <a href="#combinatorial-serialization-algorithm">Combinatorial Serialization Algorithm</a>
            passing the <a class="tref internalDFN" title="mapping_state" href="#dfn-mapping_state">mapping state</a> for the first iteration of the
            loop, and a copy of it for each subsequent iteration.
          </li>
          <li>Rotate the elements in the
            <a class="tref internalDFN" title="adjacent_unserialized_labels_list" href="#dfn-adjacent_unserialized_labels_list">adjacent unserialized labels list</a> by shifting each of
            them once to the right, moving the element at the end of the list
            to the beginning of the list.
          </li>
          <li>Decrement the <a class="tref internalDFN" title="maximum_serialization_rotations" href="#dfn-maximum_serialization_rotations">maximum serialization rotations</a> by
            <code>1</code> for each iteration.
          </li>
        </ol>
      </li>
    </ol>
  </li>
  <li>If the <a class="tref internalDFN" title="adjacent_unserialized_labels_list" href="#dfn-adjacent_unserialized_labels_list">adjacent unserialized labels list</a> is empty:
    <ol class="algorithm">
      <li>Create a <dfn title="list_of_keys" id="dfn-list_of_keys">list of keys</dfn> from the keys in the
        <a class="tref internalDFN" title="adjacent_serialized_labels_map" href="#dfn-adjacent_serialized_labels_map">adjacent serialized labels map</a> and sort it
        lexicographically.
      </li>
      <li>Add a key-value pair to the <a class="tref internalDFN" title="adjacent_info_map" href="#dfn-adjacent_info_map">adjacent info map</a> where
        the key is the <a class="tref internalDFN" title="serialization_label" href="#dfn-serialization_label-1">serialization label</a> and the value is
        an object containing the <a class="tref internalDFN" title="node_reference" href="#dfn-node_reference">node reference</a>'s label, the
        <a class="tref internalDFN" title="list_of_keys" href="#dfn-list_of_keys">list of keys</a> and the
        <a class="tref internalDFN" title="adjacent_serialized_labels_map" href="#dfn-adjacent_serialized_labels_map">adjacent serialized labels map</a>.
      </li>
      <li>Update the <a class="tref internalDFN" title="serialization_string" href="#dfn-serialization_string">serialization string</a> according to the
        <a href="#mapping-serialization-algorithm">Mapping Serialization Algorithm</a>.
      </li>
      <li>If the <a class="tref internalDFN" title="direction" href="#dfn-direction">direction</a> is <code>outgoing direction</code>
        then <dfn title="directed_serialization" id="dfn-directed_serialization">directed serialization</dfn> refers to the
        <a class="tref internalDFN" title="outgoing_serialization" href="#dfn-outgoing_serialization">outgoing serialization</a> and the
        <dfn title="directed_serialization_map" id="dfn-directed_serialization_map">directed serialization map</dfn> refers to the
        <a class="tref internalDFN" title="outgoing_serialization_map" href="#dfn-outgoing_serialization_map">outgoing serialization map</a>, otherwise it refers to the
        <a class="tref internalDFN" title="incoming_serialization" href="#dfn-incoming_serialization">incoming serialization</a> and the
        <a class="tref internalDFN" title="directed_serialization_map" href="#dfn-directed_serialization_map">directed serialization map</a> refers to the
        <a class="tref internalDFN" title="incoming_serialization_map" href="#dfn-incoming_serialization_map">incoming serialization map</a>. Compare the
        <a class="tref internalDFN" title="serialization_string" href="#dfn-serialization_string">serialization string</a> to the
        <a class="tref internalDFN" title="directed_serialization" href="#dfn-directed_serialization">directed serialization</a> according to the
        <a href="#mapping-serialization-algorithm">Serialization Comparison Algorithm</a>.
        If the <a class="tref internalDFN" title="serialization_string" href="#dfn-serialization_string">serialization string</a> is less than or equal to
        the <a class="tref internalDFN" title="directed_serialization" href="#dfn-directed_serialization">directed serialization</a>:
        <ol class="algorithm">
          <li>For each value in the <a class="tref internalDFN" title="list_of_keys" href="#dfn-list_of_keys">list of keys</a>, run the
            <a href="#node-serialization-algorithm">Node Serialization Algorithm</a>.
          </li>
	       <li>Update the <a class="tref internalDFN" title="serialization_string" href="#dfn-serialization_string">serialization string</a> according to the
	         <a href="#mapping-serialization-algorithm">Mapping Serialization Algorithm</a>.
	       </li>
	       <li>Compare the <a class="tref internalDFN" title="serialization_string" href="#dfn-serialization_string">serialization string</a> to the
	         <a class="tref internalDFN" title="directed_serialization" href="#dfn-directed_serialization">directed serialization</a> again and if it is less than
	         or equal and the length of the <a class="tref internalDFN" title="serialization_string" href="#dfn-serialization_string">serialization string</a> is
	         greater than or equal to the length of the
	         <a class="tref internalDFN" title="directed_serialization" href="#dfn-directed_serialization">directed serialization</a>, then set the
	         <a class="tref internalDFN" title="directed_serialization" href="#dfn-directed_serialization">directed serialization</a> to the
	         <a class="tref internalDFN" title="serialization_string" href="#dfn-serialization_string">serialization string</a> and set the
	         <a class="tref internalDFN" title="directed_serialization_map" href="#dfn-directed_serialization_map">directed serialization map</a> to the
	         <a class="tref internalDFN" title="serialized_labels_map" href="#dfn-serialized_labels_map">serialized labels map</a>.
	       </li>
        </ol>
      </li>
    </ol>
  </li>
</ol>

</div>

<div id="serialization-comparison-algorithm" class="section">
<h4><span class="secno">3.11.12 </span>Serialization Comparison Algorithm</h4>

<p>
The serialization comparison algorithm takes two serializations,
<a class="tref internalDFN" title="alpha" href="#dfn-alpha">alpha</a> and <a class="tref internalDFN" title="beta" href="#dfn-beta">beta</a> and returns either which of the two
is less than the other or that they are equal.
</p>

<ol class="algorithm">
  <li>Whichever serialization is an empty string is greater. If they are
    both empty strings, they are equal.</li>
  <li>Return the result of a lexicographical comparison of <a class="tref internalDFN" title="alpha" href="#dfn-alpha">alpha</a>
    and <a class="tref internalDFN" title="beta" href="#dfn-beta">beta</a> up to the number of characters in the shortest of
    the two serializations.
  </li>
</ol>
</div>

<div id="mapping-serialization-algorithm" class="section">
<h4><span class="secno">3.11.13 </span>Mapping Serialization Algorithm</h4>

<p>
The mapping serialization algorithm incrementally updates the
<a class="tref internalDFN" title="serialization_string" href="#dfn-serialization_string">serialization string</a> in a <a class="tref internalDFN" title="mapping_state" href="#dfn-mapping_state">mapping state</a>.
</p>

<ol class="algorithm">
  <li>If the <a class="tref internalDFN" title="key_stack" href="#dfn-key_stack">key stack</a> is not empty:
    <ol class="algorithm">
      <li>Pop the <dfn title="serialization_key_info" id="dfn-serialization_key_info">serialization key info</dfn> off of the
        <a class="tref internalDFN" title="key_stack" href="#dfn-key_stack">key stack</a>.
      </li>
      <li>For each <dfn title="serialization_key" id="dfn-serialization_key">serialization key</dfn> in the
        <a class="tref internalDFN" title="serialization_key_info" href="#dfn-serialization_key_info">serialization key info</a> array, starting at
        the <dfn title="serialization_key_index" id="dfn-serialization_key_index">serialization key index</dfn> from the
        <a class="tref internalDFN" title="serialization_key_info" href="#dfn-serialization_key_info">serialization key info</a>:
        <ol class="algorithm">
          <li>If the <a class="tref internalDFN" title="serialization_key" href="#dfn-serialization_key">serialization key</a> is not in the
            <a class="tref internalDFN" title="adjacent_info_map" href="#dfn-adjacent_info_map">adjacent info map</a>, push the
            <a class="tref internalDFN" title="serialization_key_info" href="#dfn-serialization_key_info">serialization key info</a> onto the
            <a class="tref internalDFN" title="key_stack" href="#dfn-key_stack">key stack</a> and exit from this loop.
          </li>
          <li>If the <a class="tref internalDFN" title="serialization_key" href="#dfn-serialization_key">serialization key</a> is a key in
            <a class="tref internalDFN" title="serialized_keys" href="#dfn-serialized_keys">serialized keys</a>, a cycle has been detected. Append
            the concatenation of the <code>_</code> character and the
            <a class="tref internalDFN" title="serialization_key" href="#dfn-serialization_key">serialization key</a> to the
            <a class="tref internalDFN" title="serialization_string" href="#dfn-serialization_string">serialization string</a>.
          </li><li>Otherwise, serialize all outgoing and incoming edges in the
            related node by performing the following steps:
            <ol class="algorithm">
              <li>Mark the <a class="tref internalDFN" title="serialization_key" href="#dfn-serialization_key">serialization key</a> as having
                been processed by adding a new key-value pair to
                <a class="tref internalDFN" title="serialized_keys" href="#dfn-serialized_keys">serialized keys</a> where the key
                is the <a class="tref internalDFN" title="serialization_key" href="#dfn-serialization_key">serialization key</a> and the value is
                <code>true</code>.
              </li>
              <li>Set the <dfn title="serialization_fragment" id="dfn-serialization_fragment">serialization fragment</dfn> to the value of
                the <a class="tref internalDFN" title="serialization_key" href="#dfn-serialization_key">serialization key</a>.</li>
              <li>Set the <a class="tref" title="adjacent_info">adjacent info</a> to the value of the
                <a class="tref internalDFN" title="serialization_key" href="#dfn-serialization_key">serialization key</a> in the
                <a class="tref internalDFN" title="adjacent_info_map" href="#dfn-adjacent_info_map">adjacent info map</a>.
              </li>
              <li>Set the <a class="tref" title="adjacent_node_label">adjacent node label</a> to the node
                <a class="tref internalDFN" title="label" href="#dfn-label">label</a> from the <a class="tref" title="adjacent_info">adjacent info</a>.
              </li>
              <li>If a mapping for the <a class="tref" title="adjacent_node_label">adjacent node label</a>
                exists in the <a class="tref" title="map_of_all_labels">map of all labels</a>:
                <ol class="algorithm">
                  <li>Append the result of the
                    <a href="">Label Serialization Algorithm</a> to the
                    <a class="tref internalDFN" title="serialization_fragment" href="#dfn-serialization_fragment">serialization fragment</a>.
                  </li>
                </ol>
              </li>
              <li>Append all of the keys in the <a class="tref" title="adjacent_info">adjacent info</a>
                to the <a class="tref internalDFN" title="serialization_fragment" href="#dfn-serialization_fragment">serialization fragment</a>.
              </li>
              <li>Append the <a class="tref internalDFN" title="serialization_fragment" href="#dfn-serialization_fragment">serialization fragment</a> to the
                <a class="tref internalDFN" title="serialization_string" href="#dfn-serialization_string">serialization string</a>.
              </li>
              <li>Push a new key info object containing the keys from the
                <a class="tref" title="adjacent_info">adjacent info</a> and an index of <code>0</code>
                onto the <a class="tref internalDFN" title="key_stack" href="#dfn-key_stack">key stack</a>.
              </li>
              <li>Recursively update the <a class="tref internalDFN" title="serialization_string" href="#dfn-serialization_string">serialization string</a>
                according to the
                <a href="#mapping-serialization-algorithm">Mapping Serialization Algorithm</a>.
              </li>
            </ol>
          </li>
        </ol>
      </li>
    </ol>
  </li>
</ol>

</div>

<div id="label-serialization-algorithm" class="section">
<h4><span class="secno">3.11.14 </span>Label Serialization Algorithm</h4>

<p>
The label serialization algorithm serializes information about a node that
has been assigned a particular <a class="tref internalDFN" title="serialization_label" href="#dfn-serialization_label-1">serialization label</a>.
</p>

<ol class="algorithm">
  <li>Initialize the <a class="tref" title="label_serialization">label serialization</a> to an empty string.</li>
  <li>Append the <code>[</code> character to the
    <a class="tref" title="label_serialization">label serialization</a>.</li>
  <li>Append all properties to the <a class="tref" title="label_serialization">label serialization</a> by
    processing each key-value pair in the <a class="tref internalDFN" title="node_reference" href="#dfn-node_reference">node reference</a>,
    excluding the
    <code>@subject</code> property. The keys should be processed in
    lexicographical order and their associated values should be processed
    in the order produced by the
    <a href="#object-comparison-algorithm">Object Comparison Algorithm</a>:
    <ol class="algorithm">
      <li>Build a string using the pattern <code>&lt;</code><strong>KEY</strong><code>&gt;</code>
        where <strong>KEY</strong> is the current key. Append string to the
        <a class="tref" title="label_serialization">label serialization</a>.</li>
      <li>The value may be a single object or an array of objects.
        Process all of the objects that are associated with the key, building
        an <dfn title="object_string" id="dfn-object_string">object string</dfn> for each item:
        <ol class="algorithm">
          <li>If the object contains an <code>@iri</code> key with a
            value that starts
            with <code>_:</code>, set the <a class="tref internalDFN" title="object_string" href="#dfn-object_string">object string</a> to
            the value <code>_:</code>. If the value does not
            start with <code>_:</code>, build the <a class="tref internalDFN" title="object_string" href="#dfn-object_string">object string</a>
            using the pattern
            <code>&lt;</code><strong>IRI</strong><code>&gt;</code>
            where <strong>IRI</strong> is the value associated with the
            <code>@iri</code> key.</li>
          <li>If the object contains a <code>@literal</code> key and a
            <code>@datatype</code> key, build the <a class="tref internalDFN" title="object_string" href="#dfn-object_string">object string</a>
            using the pattern
            <code>&quot;</code><strong>LITERAL</strong><code>&quot;^^&lt;</code><strong>DATATYPE</strong><code>&gt;</code>
            where <strong>LITERAL</strong> is the value associated with the
            <code>@literal</code> key and <strong>DATATYPE</strong> is the
            value associated with the <code>@datatype</code> key.</li>
          <li>If the object contains a <code>@literal</code> key and a
            <code>@language</code> key, build the <a class="tref internalDFN" title="object_string" href="#dfn-object_string">object string</a>
            using the pattern
            <code>&quot;</code><strong>LITERAL</strong><code>&quot;@</code><strong>LANGUAGE</strong>
            where <strong>LITERAL</strong> is the value associated with the
            <code>@literal</code> key and <strong>LANGUAGE</strong> is the
            value associated with the <code>@language</code> key.</li>
          <li>Otherwise, the value is a string. Build the
            <a class="tref internalDFN" title="object_string" href="#dfn-object_string">object string</a> using the pattern
            <code>&quot;</code><strong>LITERAL</strong><code>&quot;</code>
            where <strong>LITERAL</strong> is the value associated with the
            current key.</li>
          <li>If this is the second iteration of the loop,
            append a <code>|</code> separator character to the
            <a class="tref" title="label_serialization">label serialization</a>.</li>
          <li>Append the <a class="tref internalDFN" title="object_string" href="#dfn-object_string">object string</a> to the
            <a class="tref" title="label_serialization">label serialization</a>.</li>
        </ol>
    </li></ol>
  </li>
  <li>Append the <code>]</code> character to the
    <a class="tref" title="label_serialization">label serialization</a>.</li>
  <li>Append the <code>[</code> character to the
    <a class="tref" title="label_serialization">label serialization</a>.</li>
  <li>Append all incoming references for the current
    <a class="tref internalDFN" title="label" href="#dfn-label">label</a> to the <a class="tref" title="label_serialization">label serialization</a> by
    processing all of the items associated with the <a class="tref internalDFN" title="incoming_list" href="#dfn-incoming_list">incoming list</a>:
    <ol class="algorithm">
      <li>Build a <dfn title="reference_string" id="dfn-reference_string">reference string</dfn>
        using the pattern <code>&lt;</code><strong>PROPERTY</strong><code>&gt;</code><code>&lt;</code><strong>REFERER</strong><code>&gt;</code>
        where <strong>PROPERTY</strong> is the property associated with the
        incoming reference and <strong>REFERER</strong> is either the subject of
        the node referring to the <a class="tref internalDFN" title="label" href="#dfn-label">label</a> in the incoming reference
        or <code>_:</code> if <strong>REFERER</strong> begins with
        <code>_:</code>.
      </li><li>If this is the second iteration of the loop,
        append a <code>|</code> separator character to the
        <a class="tref" title="label_serialization">label serialization</a>.</li>
      <li>Append the <a class="tref internalDFN" title="reference_string" href="#dfn-reference_string">reference string</a> to the
        <a class="tref" title="label_serialization">label serialization</a>.</li>
    </ol>
  </li><li>Append the <code>]</code> character to the
    <a class="tref" title="label_serialization">label serialization</a>.</li>
  <li>Append all <a class="tref" title="adjacent_node_labels">adjacent node labels</a> to the
    <a class="tref" title="label_serialization">label serialization</a> by concatenating the string value
    for all of them, one after the other, to the
    <a class="tref" title="label_serialization">label serialization</a>.</li>
  <li>Push the <a class="tref" title="adjacent_node_labels">adjacent node labels</a> onto the
    <a class="tref internalDFN" title="key_stack" href="#dfn-key_stack">key stack</a> and append the result of the
    <a href="#mapping-serialization-algorithm">Mapping Serialization Algorithm</a>
    to the <a class="tref" title="label_serialization">label serialization</a>.
</li></ol>

</div>

</div>

<div id="data-round-tripping" class="section">

<h3><span class="secno">3.12 </span>Data Round Tripping</h3>

<p>When normalizing <strong>xsd:double</strong> values, implementers <em class="rfc2119" title="must">must</em>
ensure that the normalized value is a string. In order to generate the
string from a <strong>double</strong> value, output equivalent to the
<code>printf(&quot;%1.6e&quot;, value)</code> function in C <em class="rfc2119" title="must">must</em> be used where
<strong>&quot;%1.6e&quot;</strong> is the string formatter and <strong>value</strong>
is the value to be converted.</p>

<p>To convert the a double value in JavaScript, implementers can use the
following snippet of code:</p>

<pre class="example">// the variable 'value' below is the JavaScript native double value that is to be converted
(value).toExponential(6).replace(/(e(?:\+|-))([0-9])$/, '$10$2')</pre>

<p class="note">When data needs to be normalized, JSON-LD authors should
not use values that are going to undergo automatic conversion. This is due
to the lossy nature of <strong>xsd:double</strong> values.</p>

<p class="note">Some JSON serializers, such as PHP's native implementation,
backslash-escapes the forward slash character. For example, the value
<code>http://example.com/</code> would be serialized as
<code>http:\/\/example.com\/</code> in some
versions of PHP. This is problematic when generating a byte
stream for processes such as normalization. There is no need to
backslash-escape forward-slashes in JSON-LD. To aid interoperability between
JSON-LD processors, a JSON-LD serializer <em class="rfc2119" title="must not">must not</em> backslash-escape
forward slashes.</p>

<p class="issue">Round-tripping data can be problematic if we mix and
match @coerce rules with JSON-native datatypes, like integers. Consider the
following code example:</p>

<pre class="example">var myObj = { &quot;@context&quot; : {
                &quot;number&quot; : &quot;http://example.com/vocab#number&quot;,
                &quot;@coerce&quot;: {
                   &quot;xsd:nonNegativeInteger&quot;: &quot;number&quot;
                }
              },
              &quot;number&quot; : 42 };

// Map the language-native object to JSON-LD
var jsonldText = jsonld.normalize(myObj);

// Convert the normalized object back to a JavaScript object
var myObj2 = jsonld.parse(jsonldText);</pre>

<p class="issue">At this point, myObj2 and myObj will have different
values for the &quot;number&quot; value. myObj will be the number 42, while
myObj2 will be the string &quot;42&quot;. This type of data round-tripping
error can bite developers. We are currently wondering if having a
&quot;coerce validation&quot; phase in the parsing/normalization phases would be a
good idea. It would prevent data round-tripping issues like the
one mentioned above.</p>

</div>

<div id="rdf-conversion" class="section">
<h3><span class="secno">3.13 </span>RDF Conversion</h3>

<p>A JSON-LD document <em class="rfc2119" title="may">may</em> be converted to any other RDF-compatible document
format using the algorithm specified in this section.</p>

<p>
  The JSON-LD Processing Model describes processing rules for extracting RDF
  from a JSON-LD document. Note that many uses of JSON-LD may not require
  generation of RDF.
</p>

<p>
The processing algorithm described in this section is provided in
order to demonstrate how one might implement a JSON-LD to RDF processor.
Conformant implementations are only required to produce the same type and
number of triples during the output process and are not required to
implement the algorithm exactly as described.
</p>

<p class="issue">The RDF Conversion Algorithm is a work in progress.</p>

<div class="informative section" id="overview">
  <h4><span class="secno">3.13.1 </span>Overview</h4><p><em>This section is non-normative.</em></p>
  <p>
    JSON-LD is intended to have an easy to parse grammar that closely models existing
    practice in using JSON for describing object representations. This allows the use
    of existing libraries for parsing JSON.
  </p>
  <p>
    As with other grammars used for describing <a class="tref" title="Linked_Data">Linked Data</a>, a key concept is that of
    a <em>resource</em>. Resources may be of three basic types: <em>IRI</em>s, for describing
    externally named entities, <em>BNodes</em>, resources for which an external name does not
    exist, or is not known, and Literals, which describe terminal entities such as strings,
    dates and other representations having a lexical representation possibly including
    an explicit language or datatype.
  </p>
  <p>
    Data described with JSON-LD may be considered to be the representation of a graph made
    up of <a class="tref" title="subject">subject</a> and <a class="tref" title="object">object</a> resources related via a <a class="tref" title="property">property</a> resource.
    However, specific implementations may choose to operate on the document as a normal
    JSON description of objects having attributes.
  </p>
</div>

<div id="rdf-conversion-algorithm-terms" class="section">
  <h4><span class="secno">3.13.2 </span>RDF Conversion Algorithm Terms</h4>
  <dl>
    <dt><dfn title="default_graph" id="dfn-default_graph">default graph</dfn></dt>
    <dd>
      the destination graph for all triples generated by JSON-LD markup.
    </dd>
  </dl>
</div>

<div id="rdf-conversion-algorithm" class="section">
  <h4><span class="secno">3.13.3 </span>RDF Conversion Algorithm</h4>
  <p>
    The algorithm below is designed for in-memory implementations with random access to <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> elements.
  </p>
  <p>
    A conforming JSON-LD processor implementing RDF conversion <em class="rfc2119" title="must">must</em> implement a
    processing algorithm that results in the same <a class="tref internalDFN" title="default_graph" href="#dfn-default_graph">default graph</a> that the following
    algorithm generates:
  </p>

  <ol class="algorithm">
    <li id="processing-step-default-context">
      Create a new <a class="tref internalDFN" title="processor_state" href="#dfn-processor_state">processor state</a> with with the <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a> set to the
      <a class="tref internalDFN" title="initial_context" href="#dfn-initial_context">initial context</a> and <a class="tref internalDFN" title="active_subject" href="#dfn-active_subject">active subject</a> and <a class="tref internalDFN" title="active_property" href="#dfn-active_property">active property</a>
      initialized to NULL.
    </li>

    <li id="processing-step-associative">
      If a <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> is detected, perform the following steps:
      <ol class="algorithm">
        <li>
          If the <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> has a <code>@context</code> key, process the local context as
          described in <a href="#context">Context</a>.
        </li>
        <li>
          Create a new <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> by mapping the keys from the current <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> using the
          <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a> to new keys using the associated value from the current <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a>.
          Repeat the mapping until no entry is found within the <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a> for the key. Use the new
          <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> in subsequent steps.
        </li>
        <li>
          If the <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> has an <code>@iri</code> key, set the <a class="tref internalDFN" title="active_object" href="#dfn-active_object">active object</a> by
          performing <a href="#iri-expansion">IRI Expansion</a> on the associated value. Generate a
          triple representing the <a class="tref internalDFN" title="active_subject" href="#dfn-active_subject">active subject</a>, the <a class="tref internalDFN" title="active_property" href="#dfn-active_property">active property</a> and the
          <a class="tref internalDFN" title="active_object" href="#dfn-active_object">active object</a>. Return the <a class="tref internalDFN" title="active_object" href="#dfn-active_object">active object</a> to the calling location.
          <p class="issue"><code>@iri</code> really just behaves the same as <code>@subject</code>, consider consolidating them.</p>
        </li>
        <li>
          If the <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> has a <code>@literal</code> key, set the <a class="tref internalDFN" title="active_object" href="#dfn-active_object">active object</a>
          to a literal value as follows:
          <ol class="algorithm">
            <li>
              as a <a class="tref" title="typed_literal">typed literal</a> if the <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> contains a <code>@datatype</code> key
              after performing <a href="#iri-expansion">IRI Expansion</a> on the specified<code>@datatype</code>.
            </li>
            <li>
              otherwise, as a <a class="tref" title="plain_literal">plain literal</a>. If the <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> contains
              a <code>@language</code> key, use it's value to set the language of the plain literal.
            </li>
            <li>
              Generate a triple representing the <a class="tref internalDFN" title="active_subject" href="#dfn-active_subject">active subject</a>, the <a class="tref internalDFN" title="active_property" href="#dfn-active_property">active property</a> and the
              <a class="tref internalDFN" title="active_object" href="#dfn-active_object">active object</a>. Return the <a class="tref internalDFN" title="active_object" href="#dfn-active_object">active object</a> to the calling location.
            </li>
          </ol>
        </li>
        <li id="processing-step-subject">If the <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> has a <code>@subject</code> key:
          <ol class="algorithm">
            <li>
              If the value is a <a class="tref internalDFN" title="string" href="#dfn-string">string</a>, set the <a class="tref internalDFN" title="active_object" href="#dfn-active_object">active object</a> to the result of performing
              <a href="#iri-expansion">IRI Expansion</a>. Generate a
              triple representing the <a class="tref internalDFN" title="active_subject" href="#dfn-active_subject">active subject</a>, the <a class="tref internalDFN" title="active_property" href="#dfn-active_property">active property</a> and the
              <a class="tref internalDFN" title="active_object" href="#dfn-active_object">active object</a>. Set the <a class="tref internalDFN" title="active_subject" href="#dfn-active_subject">active subject</a> to the <a class="tref internalDFN" title="active_object" href="#dfn-active_object">active object</a>.
            </li>
            <li>
              Create a new <a class="tref internalDFN" title="processor_state" href="#dfn-processor_state">processor state</a> using copies of the <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a>,
              <a class="tref internalDFN" title="active_subject" href="#dfn-active_subject">active subject</a> and <a class="tref internalDFN" title="active_property" href="#dfn-active_property">active property</a> and process the value
              starting at <a href="#processing-step-associative">Step 2</a>, set the <a class="tref" title="active__subject">active
              subject</a> to the result and proceed using the previous <a class="tref internalDFN" title="processor_state" href="#dfn-processor_state">processor state</a>.
            </li>
          </ol>
        </li>
        <li>
          If the <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> does not have a <code>@subject</code> key, set the <a class="tref" title="active__object">active
          object</a> to newly generated <dfn title="blank_node_identifier" id="dfn-blank_node_identifier">blank node identifier</dfn>. Generate a triple
          representing the <a class="tref internalDFN" title="active_subject" href="#dfn-active_subject">active subject</a>, the <a class="tref internalDFN" title="active_property" href="#dfn-active_property">active property</a> and the
          <a class="tref internalDFN" title="active_object" href="#dfn-active_object">active object</a>. Set the <a class="tref internalDFN" title="active_subject" href="#dfn-active_subject">active subject</a> to the <a class="tref" title="active__object">active
          object</a>.
        </li>
        <li>
          For each key in the <a class="tref internalDFN" title="JSON_object" href="#dfn-json_object">JSON object</a> that has not already been processed, perform
          the following steps:
          <ol class="algorithm">
            <li>
              If the key is <code>@type</code>, set the <a class="tref internalDFN" title="active_property" href="#dfn-active_property">active property</a>
              to <code>rdf:type</code>.
            </li>
            <li>Otherwise, set the <a class="tref internalDFN" title="active_property" href="#dfn-active_property">active property</a> to the result of performing
            <a href="#iri-expansion">IRI Expansion</a> on the key.</li>
            <li>
              Create a new <a class="tref internalDFN" title="processor_state" href="#dfn-processor_state">processor state</a> copies of the <a class="tref internalDFN" title="active_context" href="#dfn-active_context">active context</a>,
              <a class="tref internalDFN" title="active_subject" href="#dfn-active_subject">active subject</a> and <a class="tref internalDFN" title="active_property" href="#dfn-active_property">active property</a> and process the value
              starting at <a href="#processing-step-associative">Step 2</a> and proceed using the
              previous <a class="tref internalDFN" title="processor_state" href="#dfn-processor_state">processor state</a>.
            </li>
          </ol>
        </li>
        <li>
          Return the <a class="tref internalDFN" title="active_object" href="#dfn-active_object">active object</a> to the calling location.
        </li>
      </ol>
    </li>

    <li>
      If a regular <a class="tref internalDFN" title="array" href="#dfn-array">array</a> is detected, process each value in the <a class="tref internalDFN" title="array" href="#dfn-array">array</a> by doing the following
      returning the result of processing the last value in the <a class="tref internalDFN" title="array" href="#dfn-array">array</a>:

      <ol class="algorithm">
        <li>
          Create a new <a class="tref internalDFN" title="processor_state" href="#dfn-processor_state">processor state</a> using copies of the <a class="tref" title="active__context">active
          context</a>, <a class="tref internalDFN" title="active_subject" href="#dfn-active_subject">active subject</a> and <a class="tref internalDFN" title="active_property" href="#dfn-active_property">active property</a> and process the value
          starting at <a href="#processing-step-associative">Step 2</a> then proceed using the previous
          <a class="tref internalDFN" title="processor_state" href="#dfn-processor_state">processor state</a>.
        </li>
      </ol>
    </li>

    <li>
      If a <a class="tref internalDFN" title="string" href="#dfn-string">string</a> is detected:
      <ol class="algorithm">
        <li>
          If the <a class="tref internalDFN" title="active_property" href="#dfn-active_property">active property</a> is the target of a <code>@iri</code> coercion,
          set the <a class="tref internalDFN" title="active_object" href="#dfn-active_object">active object</a> by
          performing <a href="#iri-expansion">IRI Expansion</a> on the string.
        </li>
        <li>
          Otherwise, if the <a class="tref internalDFN" title="active_property" href="#dfn-active_property">active property</a> is the target of coercion,
          set the <a class="tref internalDFN" title="active_object" href="#dfn-active_object">active object</a> by creating a <a class="tref" title="typed_literal">typed literal</a> using
          the string and the coercion key as the datatype IRI.
        </li>
        <li>
          Otherwise, set the <a class="tref internalDFN" title="active_object" href="#dfn-active_object">active object</a> to a <a class="tref" title="plain_literal">plain literal</a> value created from
          the string.
        </li>
      </ol>
      Generate a
      triple representing the <a class="tref internalDFN" title="active_subject" href="#dfn-active_subject">active subject</a>, the <a class="tref internalDFN" title="active_property" href="#dfn-active_property">active property</a> and the
      <a class="tref internalDFN" title="active_object" href="#dfn-active_object">active object</a>.
    </li>

    <li>
      If a <a class="tref internalDFN" title="number" href="#dfn-number">number</a> is detected, generate a <a class="tref" title="typed_literal">typed literal</a> using a string representation of
      the value with datatype set to either <code>xsd:integer</code> or
      <code>xsd:double</code>, depending on if the value contains a
      fractional and/or an exponential component. Generate a triple using the <a class="tref" title="active__subject">active
      subject</a>, <a class="tref internalDFN" title="active_property" href="#dfn-active_property">active property</a> and the generated typed literal.
    </li>

    <li>
      Otherwise, if <strong>true</strong> or <strong>false</strong> is detected,
      generate a triple using the <a class="tref internalDFN" title="active_subject" href="#dfn-active_subject">active subject</a>, <a class="tref internalDFN" title="active_property" href="#dfn-active_property">active property</a>
      and a <a class="tref" title="typed_literal">typed literal</a> value created from the string representation of the
      value with datatype set to <code>xsd:boolean</code>.
    </li>
  </ol>
</div>

<div class="appendix section" id="acknowledgements">
<h4><span class="secno">3.13.4 </span>Acknowledgements</h4>

<p>The editors would like to thank Mark Birbeck, who provided a great deal of
the initial push behind the JSON-LD work via his work on RDFj,
Dave Longley, Dave Lehn and Mike Johnson who reviewed, provided feedback, and
performed several implementations of the specification, and Ian Davis, who
created RDF/JSON. Thanks also to Nathan Rixham, Bradley P. Allen,
Kingsley Idehen, Glenn McDonald, Alexandre Passant, Danny Ayers, Ted
Thibodeau Jr., Olivier Grisel, Niklas Lindström, Markus Lanthaler, and Richard
Cyganiak for their input on the specification. Another huge thank you goes out
to Dave Longley who designed many of the algorithms used in this specification,
including the normalization algorithm which was a monumentally difficult
design challenge.
</p>
</div>



</div></div><div id="references" class="appendix section">
<!-- OddPage -->
<h2><span class="secno">A. </span>References</h2><div id="normative-references" class="section"><h3><span class="secno">A.1 </span>Normative references</h3><dl class="bibliography"><dt id="bib-JSON-LD">[JSON-LD]</dt><dd>Manu Sporny, Gregg Kellogg, et al. <a href="http://json-ld.org/spec/latest/json-ld-syntax/"><cite>The JSON-LD Syntax</cite></a> Latest. W3C Editor's Draft. URL: <a href="http://json-ld.org/spec/latest/json-ld-syntax/">http://json-ld.org/spec/latest/json-ld-syntax/</a>
</dd><dt id="bib-RDF-CONCEPTS">[RDF-CONCEPTS]</dt><dd>Graham Klyne; Jeremy J. Carroll. <a href="http://www.w3.org/TR/2004/REC-rdf-concepts-20040210"><cite>Resource Description Framework (RDF): Concepts and Abstract Syntax.</cite></a> 10 February 2004. W3C Recommendation. URL: <a href="http://www.w3.org/TR/2004/REC-rdf-concepts-20040210">http://www.w3.org/TR/2004/REC-rdf-concepts-20040210</a> 
</dd><dt id="bib-RFC3986">[RFC3986]</dt><dd>T. Berners-Lee; R. Fielding; L. Masinter. <a href="http://www.ietf.org/rfc/rfc3986.txt"><cite>Uniform Resource Identifier (URI): Generic Syntax.</cite></a> January 2005. Internet RFC 3986. URL: <a href="http://www.ietf.org/rfc/rfc3986.txt">http://www.ietf.org/rfc/rfc3986.txt</a> 
</dd><dt id="bib-RFC4627">[RFC4627]</dt><dd>D. Crockford. <a href="http://www.ietf.org/rfc/rfc4627.txt"><cite>The application/json Media Type for JavaScript Object Notation (JSON)</cite></a> July 2006. Internet RFC 4627. URL: <a href="http://www.ietf.org/rfc/rfc4627.txt">http://www.ietf.org/rfc/rfc4627.txt</a>
</dd><dt id="bib-WEBIDL">[WEBIDL]</dt><dd>Cameron McCormack. <a href="http://www.w3.org/TR/2008/WD-WebIDL-20081219"><cite>Web IDL.</cite></a> 19 December 2008. W3C Working Draft. (Work in progress.) URL: <a href="http://www.w3.org/TR/2008/WD-WebIDL-20081219">http://www.w3.org/TR/2008/WD-WebIDL-20081219</a> 
</dd></dl></div><div id="informative-references" class="section"><h3><span class="secno">A.2 </span>Informative references</h3><dl class="bibliography"><dt id="bib-ECMA-262">[ECMA-262]</dt><dd><a href="http://www.ecma-international.org/publications/standards/Ecma-262.htm"><cite>ECMAScript Language Specification, Third Edition.</cite></a> December 1999. URL: <a href="http://www.ecma-international.org/publications/standards/Ecma-262.htm">http://www.ecma-international.org/publications/standards/Ecma-262.htm</a> 
</dd><dt id="bib-MICRODATA">[MICRODATA]</dt><dd>Ian Hickson; et al. <a href="http://www.w3.org/TR/microdata/"><cite>Microdata</cite></a> 04 March 2010. W3C Working Draft. URL: <a href="http://www.w3.org/TR/microdata/">http://www.w3.org/TR/microdata/</a> 
</dd><dt id="bib-MICROFORMATS">[MICROFORMATS]</dt><dd><a href="http://microformats.org"><cite>Microformats</cite></a>. URL: <a href="http://microformats.org">http://microformats.org</a> 
</dd><dt id="bib-RDFA-CORE">[RDFA-CORE]</dt><dd>Shane McCarron; et al. <a href="http://www.w3.org/TR/2011/WD-rdfa-core-20110331"><cite>RDFa Core 1.1: Syntax and processing rules for embedding RDF through attributes.</cite></a> 31 March 2011. W3C Working Draft. URL: <a href="http://www.w3.org/TR/2011/WD-rdfa-core-20110331">http://www.w3.org/TR/2011/WD-rdfa-core-20110331</a> 
</dd></dl></div></div></body></html>
